很久以前做的一个东西，当时是对R排序之后树状数组暴力统计当前区间的前缀和。每有一个元素出现在R的范围内，就解除他的同样元素的影响，在他上一个同样元素曾经+1的位置给他-1。因为已经对R进行排序了，下一个询问一定会更容易包含后面出现的那一个。
今天又演了居然想尺取，做不到做不到，L是会不断变化的，不满足尺取的条件。
然后重写的时候发现
last[a[R]]=R++;
与
last[a[R]]=R;++R;
并不等价。
看来会改变的同一个变量最好只在一句话中出现一次。
#includeusing namespace std;typedef long long ll;struct Query { int l, r, id;} q[1000005];bool cmp1(const Query& q1, const Query& q2) { return q1.r != q2.r ? q1.r < q2.r : q1.l < q2.l;}int ans[1000005];int n, m, a[1000005];int last[1000005], cnt;int bit[1000005];inline int Sum(int x) { int res = 0; for(; x; x -= x & -x) res += bit[x]; return res;}inline void Add(int x, int v) { for(; x <= n; x += x & -x) bit[x] += v;}int main() {#ifdef Yinku freopen("Yinku.in", "r", stdin);#endif // Yinku scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); scanf("%d", &m); for(int i = 1; i <= m; ++i) { scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i; } sort(q + 1, q + 1 + m, cmp1); int R = 1; for(int i = 1; i <= m; ++i) { while(R <= q[i].r) { if(last[a[R]]) Add(last[a[R]], -1); Add(R, 1); last[a[R]] = R; ++R; } ans[q[i].id] = Sum(q[i].r) - Sum(q[i].l - 1); } for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]); return 0;}
在不引起混淆的情况下，使用运算符重载会比使用外部cmp快10%。
#includeusing namespace std;typedef long long ll;struct Query { int l, r, id; bool operator<(const Query& q2) { return r < q2.r; }} q[1000005];int ans[1000005];int n, m, a[1000005];int last[1000005], cnt;int bit[1000005];inline int Sum(int x) { int res = 0; for(; x; x -= x & -x) res += bit[x]; return res;}inline void Add(int x, int v) { for(; x <= n; x += x & -x) bit[x] += v;}int main() {#ifdef Yinku freopen("Yinku.in", "r", stdin);#endif // Yinku scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); scanf("%d", &m); for(int i = 1; i <= m; ++i) { scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i; } sort(q + 1, q + 1 + m); int R = 1; for(int i = 1; i <= m; ++i) { while(R <= q[i].r) { if(last[a[R]]) Add(last[a[R]], -1); Add(R, 1); last[a[R]] = R; ++R; } ans[q[i].id] = Sum(q[i].r) - Sum(q[i].l - 1); } for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]); return 0;}