莫队算法（可修改）
2020-12-13 14:20
阅读：516
对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。
莫队可以修改？那不是爆炸了吗。这类爆炸的问题被称为带修莫队（可持久化莫队）。
按照美妙类比思想，可以引入一个“修改时间”，表示当前询问是发生在前Time个修改操作后的。也就是说，在进行莫队算法时，看看当前的询问和时间指针是否相符，然后进行时光倒流或者时光推移操作来保证答案正确性。
Sort的构造：仅靠原来的sort关键字会使得枚举每个询问都可能因为时间指针移动的缘故要移动n次，总共就n^2次，那还不如写暴力。为了防止这样的事情发生，再加入第三关键字Tim：
1 #include2 using namespace std; 3 const int maxn=10000+10; 4 struct Query{ 5 int l,r,Tim,ID; 6 }q[maxn]; 7 struct Change{ 8 int pos,New,Old; 9 }c[maxn]; 10 int s[maxn],Be[maxn]; 11 int now[maxn],ans[maxn]; 12 int color[maxn*100]; 13 int Ans,l=1,r; 14 bool cmp(Query a,Query b) 15 { 16 return Be[a.l]==Be[b.l]?(Be[a.r]==Be[b.r]?a.Tim b.l; 17 } 18 void revise(int x,int d) 19 { 20 color[x]+=d; 21 if(d>0) Ans+=color[x]==1; 22 if(d0) Ans-=color[x]==0; 23 } 24 void going(int x,int d) 25 { 26 if(lr) 27 revise(d,1),revise(s[x],-1); 28 s[x]=d; 29 } 30 int main() 31 { 32 int n,m; 33 scanf("%d%d",&n,&m); 34 int unit=pow(n,2.0/3); 35 for(int i=1;i){ 36 scanf("%d",&s[i]); 37 now[i]=s[i]; 38 Be[i]=i/unit+1; //分块 39 } 40 int Time=0,t=0; 41 while(m--){ 42 char sign; int x,y; 43 scanf(" %c %d%d",&sign,&x,&y); 44 if(sign==‘Q‘) q[++t]=(Query){x,y,Time,t}; 45 else c[++Time]=(Change){x,y,now[x]},now[x]=y; 46 } 47 sort(q+1,q+t+1,cmp); 48 int T=0; 49 for(int i=1;i){ 50 while(T 1].pos,c[T+1].New),T++; 51 while(T>q[i].Tim) going(c[T].pos,c[T].Old),T--; 52 while(l1),l++; 53 while(l>q[i].l) revise(s[l-1],1),l--; 54 while(r1],1),r++; 55 while(r>q[i].r) revise(s[r],-1),r--; 56 ans[q[i].ID]=Ans; 57 } 58 for(int i=1;i) 59 printf("%d\n",ans[i]); 60 return 0; 61 }
上一篇：WPF之DataGrid应用
评论
亲，登录后才可以留言！