【题意】给定n个数字，m次操作，每次询问区间不同数字的个数，或修改某个位置的数字。n,m<=10^4，ai<=10^6。
【算法】带修改的莫队算法
【题解】对于询问(x,y,t)，其中t是前面的修改次数，所有修改记录改前和改后。
首先按belong[x]，然后按belong[y]，最后按t排序。（块大小n^(2/3)）
移动询问，先移动t，然后移动x和y，运用对称差操作实现。如果移动t前修改格访问过，先删除影响，修改，再加回。
区间莫队需要注意的还有操作顺序问题，区间先拓展再收缩，以及修改的开闭边界问题需要特别注意（左右是不同的）。
哦还有还有，初始是(0,0,0)的话，令vis[0]=1。
为什么我说得这么草率？因为写完了糖果公园后就真的没什么好说的了……当然还是在区间移动上面栽了一下233。
#include<cmath> #include<cstdio> #include<algorithm> using namespace std; const int maxn=10010; int belong[maxn],n,m,pre[maxn],c[maxn],d[1000010],ans=0,c0,c1,ANS[maxn]; bool vis[maxn]; struct q{int x,y,t,id;}b[maxn]; struct mo{int x,y,pre;}a[maxn]; bool cmp(q a,q b){return belong[a.x]<belong[b.x]||(belong[a.x]==belong[b.x]&&belong[a.y]<belong[b.y])|| (belong[a.x]==belong[b.x]&&belong[a.y]==belong[b.y]&&a.t<b.t);} void solve(int x){if(!vis[x])ans+=(++d[c[x]]==1);else ans-=(--d[c[x]]==0);// vis[x]^=1; } void modify(int x,int y){if(!vis[x])c[x]=y;else solve(x),c[x]=y,solve(x); } char s[10]; int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&c[i]),pre[i]=c[i];for(int i=1;i<=m;i++){int u,v;scanf("%s%d%d",s,&u,&v);if(s[0]=='R')a[++c0]=(mo){u,v,pre[u]},pre[u]=v;else {if(u>v)swap(u,v);b[++c1]=(q){u,v,c0,c1};}}int Q=(int)pow(n,2.0/3);for(int i=1;i<=n;i++)belong[i]=(i-1)/Q+1;sort(b+1,b+c1+1,cmp);vis[0]=1;// for(int i=1;i<=c1;i++){for(int j=b[i-1].t+1;j<=b[i].t;j++)modify(a[j].x,a[j].y);for(int j=b[i-1].t;j>b[i].t;j--)modify(a[j].x,a[j].pre);for(int j=b[i-1].y+1;j<=b[i].y;j++)solve(j);// for(int j=b[i-1].x-1;j>=b[i].x;j--)solve(j);for(int j=b[i-1].x;j<b[i].x;j++)solve(j);for(int j=b[i-1].y;j>b[i].y;j--)solve(j);ANS[b[i].id]=ans;}for(int i=1;i<=c1;i++)printf("%d\n",ANS[i]);return 0; }