第一道带修改的莫队。学习ing
传送门：Dynamic len(set(a[L:R]))
当然也可以访问vjudge。 另类传送门
题意：
有一个序列，对于这个序列有两种操作。
1、询问[l, r]这个区间里有多少个不同的数
2、修改某个位置的值。
如果没写过莫队的修改，应该会能想到树套树（orz但是本人蒟蒻不会写树套树啊）。
但是有了莫队之后情况就不一样了。代码量比树套树要少很多。莫队的修改：
分块的时候要分成 2 / 3块(没证明过)。
时间复杂度为 n53
分块排序的时候，先按左端点的块排序，再按右端点的块排序。
最后按修改时间排序。这里的修改时间为，这个询问操作前面出现过多少次修改操作。
对于每一次查询，先将他退回或前进到修改的时间。
再进行分块的查询。有没有一点时光倒流的感觉呢。这里要注意，以前写莫队每太在意l指针和r指针的交错，这道题如果移动的时候交错了就会wa。
所以，我们应该优先移动r指针向右，再移动l指针向左，剩下两个随意操作。
这要能保证这两个指针不会错位。就是不会出现r < l的情况
#include <bits/stdc++.h>#define MAXN 1000005using namespace std;struct Question {int l, r, idx, time; //time 代表修改的时间
} qsn[MAXN];struct Modify {int x, last, val;
} mod[MAXN]; int pos[MAXN];
int flag[MAXN];
int a[MAXN];
int lans[MAXN];
int last[MAXN];
bool mark[MAXN];
int q, ans, n, cnt;int cmp(Question a, Question b) {if (pos[a.l] != pos[b.l]) {return pos[a.l] < pos[b.l];}if (pos[a.r] != pos[b.r]) {return pos[a.r] < pos[b.r];}return a.time < b.time;
}void clear() {memset(flag, 0, sizeof(flag));memset(mark, false, sizeof(mark));cnt = q = ans = 0;
}void add(int x) {if (!flag[a[x]]) {ans++;}flag[a[x]]++;mark[x] = true;
}void del(int x) {flag[a[x]]--;if (!flag[a[x]]) {ans--;}mark[x] = false;
}void modify(int x, int v) {if (mark[x]) {del(x);a[x] = v;add(x);} else {a[x] = v;}
}void solve() {sort(qsn + 1, qsn + q + 1, cmp);int l = 1, r = 0, time = 0;for (int i = 1; i <= q; i++) {while (time < qsn[i].time) {time++;modify(mod[time].x, mod[time].val);}while (time > qsn[i].time) { //时光倒流modify(mod[time].x, mod[time].last);time--;}while (r < qsn[i].r) {add(++r);}while (l > qsn[i].l) {add(--l);}while (r > qsn[i].r) {del(r--);}while (l < qsn[i].l) {del(l++);}lans[qsn[i].idx] = ans;}for (int i = 1; i <= q; i++) {printf("%d\n", lans[i]);}
}int main() {char opt[10];int x, y, m;while (~scanf("%d %d", &n, &m)) {int s = pow(n, 2.0 / 3) + 1; //这里如果是带修改的要2/3 for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);pos[i] = i / s;last[i] = a[i];}clear();for (int i = 1; i <= m; i++) {scanf("%s %d %d", opt, &x, &y);x++;if (opt[0] == 'Q') {qsn[++q].idx = q;qsn[q].l = x;qsn[q].r = y;qsn[q].time = cnt;} else {mod[++cnt].x = x;mod[cnt].last = last[x]; //记录修改过来的值 mod[cnt].val = y;last[x] = y;}}solve();}
}/*
7 4
1 2 1 3 2 1 4
Q 1 6
M 3 2
Q 1 6
Q 3 5
*/