UVA 12345 Dynamic len(set(a[L:R])) 分块或带修改莫队

题目：

https://vjudge.net/problem/UVA-12345

题意：

给出一个有n个元素的数组，有以下两种操作：Q x y，求出区间[x,y)内不同元素的个数，M x y，把第x个元素的值修改为y。注意题目中的下标是从0开始的

思路：

我写了分块和带修改莫队两种做法。首先讲分块法，对于每个位置i，我们记录前一个相同元素的坐标，记为pre[i]，然后分块，块内按pre数组排序，等到查询的时候区间[l,r)时，如果pre[i] < l，说明位置i的元素在查询区间内第一次出现，计数加1，如果pre[i] >= l，说明位置i的元素不是第一次出现，前面已经统计过了，故计数不变。按照这个思路，块内的pre数组是有序的，故可以二分快速确定第一次出现的元素的个数，不在完整块内的元素直接暴力统计即可。对于修改位置i的元素为v，我们可以发现，最多只需要找到四个值，皆可以完成修改，即找到位置i的前一个相同元素j和后一个相同元素的位置k，把k的前驱更新为j；找到位置i之前的第一个等于v的元素的位置x和之后第一个等于v的元素的位置y，把y的前驱更新为i，i的前驱更新为x，注意前驱不存在就更新为0，这样就完成了修改

#include <bits/stdc++.h> using namespace std; const int N = 50000 + 10, M = 1000000 + 10, INF = 0x3f3f3f3f; int n, m; int block, sz; int pos[N], L[N], R[N], pre[N]; int last[M]; int a[N], b[N]; void reset(int x) { for(int i = L[x]; i <= R[x]; i++) pre[i] = b[i]; sort(pre + L[x], pre + R[x] + 1); } void init() { block = sqrt(n); sz = n / block; if(n % block) sz++; for(int i = 1; i <= n; i++) pos[i] = (i-1) / block + 1; for(int i = 1; i <= sz; i++) { L[i] = (i-1) * block + 1; R[i] = i * block; } R[sz] = n; memset(last, 0, sizeof last); for(int i = 1; i <= n; i++) { b[i] = last[a[i]]; last[a[i]] = i; } for(int i = 1; i <= sz; i++) reset(i); } void update(int x, int v) { if(a[x] == v) return; int idx = -1, idv = -1; for(int i = x+1; i <= n; i++) { if(a[i] == a[x] && idx == -1) idx = i; else if(a[i] == v && idv == -1) idv = i; if(idx != -1 && idv != -1) break; } if(idv != -1) b[idv] = x, reset(pos[idv]); idv = x; for(int i = x-1; i >= 1; i--) { if(a[i] == a[x] && idx != -1) b[idx] = i, reset(pos[idx]), idx = -1; if(a[i] == v && idv != -1) b[idv] = i, reset(pos[idv]), idv = -1; if(idx == -1 && idv == -1) break; } if(idx != -1) b[idx] = 0, reset(pos[idx]); if(idv != -1) b[idv] = 0, reset(pos[idv]); a[x] = v; } int query(int l, int r) { int lb = pos[l], rb = pos[r]; int ans = 0; if(lb == rb) { for(int i = l; i <= r; i++) if(b[i] < l) ans++; } else { for(int i = l; i <= R[lb]; i++) if(b[i] < l) ans++; for(int i = L[rb]; i <= r; i++) if(b[i] < l) ans++; for(int i = lb + 1; i < rb; i++) ans += lower_bound(pre + L[i], pre + R[i] + 1, l) - (pre + L[i]); } return ans; } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); init(); char ch; int x, y; for(int i = 1; i <= m; i++) { scanf(" %c%d%d", &ch, &x, &y); if(ch == 'Q') printf("%d\n", query(x+1, y)); else update(x+1, y); } return 0; }

带修改莫队和普通莫队其实差不多，普通莫队按两个关键字对询问排序，首先按左端点所在的块从小到大排序，否则按右端点排序。带修改莫队按三个关键字排序，第三个关键字是本次询问时前一个修改的位置，首先按左端点所在的块从小到大排序，否则按右端点所在的块从小到大排序，否则按第三个关键字直接排序。然后查询时，暴力还原修改到本次查询时的状态，其他的就都一样了。代码中的vis[i]为1时代表这个值被统计在答案中，否则不是

#include <bits/stdc++.h> using namespace std; const int N = 50000 + 10, M = 1000000 + 10; struct node { int l, r, id, pre; }g[N]; struct { int x, v, o; }q[N]; int n, m; int block, tot, top, val; int a[N], last[N], pos[N], ans[N], num[M]; bool vis[N]; bool cmp(node a, node b) { // return (pos[a.l] < pos[b.l]) || (pos[a.l]==pos[b.l] && pos[a.r] < pos[b.r]) // || (pos[a.l] == pos[b.l] && pos[a.r] == pos[b.r] && a.pre < b.pre); if(pos[a.l] == pos[b.l] && pos[a.r] == pos[b.r]) return a.pre < b.pre; else if(pos[a.l] == pos[b.l]) return pos[a.r] < pos[b.r]; else return pos[a.l] < pos[b.l]; } void init() { //block = sqrt(n); block = 1300;//设为1300比sqrt(n)块，蜜汁。。。 for(int i = 1; i <= n; i++) pos[i] = (i-1) / block + 1; tot = top = 0; } void update(int x) { if(vis[x]) { if(--num[a[x]] == 0) val--; } else { if(++num[a[x]] == 1) val++; } vis[x] ^= 1; } void restore(int x, int v) { if(vis[x]) { update(x); a[x] = v; update(x); } else a[x] = v; } void work() { sort(g + 1, g + 1 + tot, cmp); val = 0; int l = 1, r = 0, now = 0; for(int i = 1; i <= tot; i++) { while(now < g[i].pre) ++now, restore(q[now].x, q[now].v); while(now > g[i].pre) restore(q[now].x, q[now].o), --now; while(r < g[i].r) update(++r); while(r > g[i].r) update(r--); while(l < g[i].l) update(l++); while(l > g[i].l) update(--l); ans[g[i].id] = val; } for(int i = 1; i <= tot; i++) printf("%d\n", ans[i]); } int main() { scanf("%d%d", &n, &m); init(); for(int i = 1; i <= n; i++) scanf("%d", &a[i]), last[i] = a[i]; char ch; int x, y; for(int i = 1; i <= m; i++) { scanf(" %c%d%d", &ch, &x, &y); x++; if(ch == 'Q') g[++tot].l = x, g[tot].r = y, g[tot].id = tot, g[tot].pre = top; else q[++top].x = x, q[top].v = y, q[top].o = last[x], last[x] = y; } work(); return 0; }