题解 P1903 【【模板】分块/带修改莫队（数颜色）】

带修改的莫队，和原版莫队相比，多了一个时间轴 原版莫队是将区间(l,r)视为点(l,r)，带修改的即加一维时间轴(l,r,t) 对于t轴的移动可以保存每次修改，如果修改在(l,r)间则更新 分块方法可以参照原版莫队，先将l分块，再讲r分块，同一块的按t排序 块大小为  可以达到最快的理论复杂度  ，证明如下 设分块大小为a，莫队算法时间复杂度主要为t轴移动，同r块l,r移动，l块间的r移动三部分 t轴移动的复杂度为  ，同r块l,r移动复杂度为  ，l块间的r移动复杂度为  三个函数max的最小值当a为  取得，为  代码如下 ```cpp #include<cstdio> #include<algorithm> #include<cmath> using namespace std; #define fo(a,b,c) for(int a=b;a<=c;a++) #define go(a,b,c) for(int a=b;a>=c;a--) int read(){ int a=0,f=0;char c=getchar(); for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1; for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0'; return f?-a:a; } const int N=10001; int a[N],p[1000001],ans[N],divi; struct nod{int pla,pre,suc;}cg[N]; struct node{int l,r,t,bel;}ls[N]; int cmp(node a,node b){ if(a.l/divi!=b.l/divi)return a.l/divi<b.l/divi; if(a.r/divi!=b.r/divi)return a.r/divi<b.r/divi; return a.t<b.t; } int main(){ int n=read(),m=read(),ln=0,tn=0,l=1,r=0,t=0,num=0; fo(i,1,n)a[i]=read(); fo(i,1,m){ scanf("\n"); if(getchar()=='R'){//如果读入修改则记录修改的地点，修改前的数字和修改后的数字 ++tn;cg[tn].pla=read(),cg[tn].suc=read(); cg[tn].pre=a[cg[tn].pla]; a[cg[tn].pla]=cg[tn].suc; } else ls[++ln]=(node){read(),read(),tn,ln}; } divi=ceil(exp((log(n)+log(tn))/3));//分块大小 go(i,tn,1)a[cg[i].pla]=cg[i].pre; sort(ls+1,ls+ln+1,cmp); fo(i,1,m){ while(ls[i].l<l)num+=!p[a[--l]]++; while(ls[i].l>l)num-=!--p[a[l++]];//l移动 while(ls[i].r>r)num+=!p[a[++r]]++; while(ls[i].r<r)num-=!--p[a[r--]];//r移动 while(ls[i].t<t){ int pla=cg[t].pla; if(l<=pla&&pla<=r)num-=!--p[a[pla]]; a[pla]=cg[t--].pre; if(l<=pla&&pla<=r)num+=!p[a[pla]]++; }; while(ls[i].t>t){ int pla=cg[++t].pla; if(l<=pla&&pla<=r)num-=!--p[a[pla]]; a[pla]=cg[t].suc; if(l<=pla&&pla<=r)num+=!p[a[pla]]++; };//t移动 ans[ls[i].bel]=num; } fo(i,1,ln)printf("%d\n",ans[i]); return 0; } ```