带修改的莫队：
在普通莫队的基础上维护了一个修改的结构体。加上了一维时间戳。
对于查询操作，记录最近的修改位置。然后在查询操作中。
对于查询之后，还需要去维护一个修改操作，并且要维护对答案的影响。
这题有点卡常，还好我卡的好(逃
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 2e5+5; const int M = 1e6+5; const LL Mod = 199999; #define rg register #define pi acos(-1) #define INF 1e18 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; void FRE(){ /*freopen("data1.in","r",stdin); freopen("data1.out","w",stdout);*/} int n,m,val[N],bel[N],sz,bnum,ctot = 0,qtot = 0,cnt = 0,vis[M],ans[N];//cnt记录不同颜色的个数 struct Modify{int pos,val,pre;}cg[N]; struct query{int L,r,t,id;}q[N]; bool cmp(query a,query b){ return bel[a.L] ^ bel[b.L] ? bel[a.L] < bel[b.L] : (bel[a.r] ^ bel[b.r] ? bel[a.r] < bel[b.r] : a.t < b.t); } void del(int x) { x = val[x]; if(vis[x] == 1) cnt--; vis[x]--; } void add(int x) { x = val[x]; if(vis[x] == 0) cnt++; vis[x]++; } void work(int tim,int i) { if(cg[tim].pos >= q[i].L && cg[tim].pos <= q[i].r) { if(vis[val[cg[tim].pos]] == 1) cnt--; if(vis[cg[tim].val] == 0) cnt++; vis[val[cg[tim].pos]]--; vis[cg[tim].val]++; } swap(val[cg[tim].pos],cg[tim].val); } int main() { n = read(),m = read(); sz = pow(n,2.0/3.0); bnum = ceil(double(n)/sz); for(rg int i = 1;i <= bnum;++i) for(rg int j = (i-1)*sz+1;j <= i*sz;++j) bel[j] = i; //分块预处理 for(rg int i = 1;i <= n;++i) val[i] = read(); for(rg int i = 1;i <= m;++i) { char c[2];scanf("%s",&c); if(c[0] == 'Q') { q[++qtot].L = read(),q[qtot].r = read(); q[qtot].t = ctot,q[qtot].id = qtot; } else cg[++ctot].pos = read(),cg[ctot].val = read(); } sort(q+1,q+qtot+1,cmp); int L = 1,r = 0,tim = 0; for(rg int i = 1;i <= qtot;++i) { while(L < q[i].L) del(L++); while(L > q[i].L) add(--L); while(r < q[i].r) add(++r); while(r > q[i].r) del(r--); while(tim < q[i].t) work(++tim,i); while(tim > q[i].t) work(tim--,i); ans[q[i].id] = cnt; } for(rg int i = 1;i <= qtot;++i) printf("%d ",ans[i]); system("pause"); }