毒瘤莫队卡常题，卡了一早上的常数，才开O2勉强过。
带修莫队模板题。
普通莫队要离线下来做，遇到这种带修改的题目直接就萎了，但是全国广大的OIer们在莫队的基础上，发明了带修莫队这种玄学算法。
具体来说就是给修改和求值打上时间戳，然后在普通莫队双指针的基础上增加一个指针tim指向时间，在这一个维度上面跳来跳去，直到跳到左指针指向左端点，右指针指向右端点，tim指针指向当前求值的时间戳为止。
排序依然是按左端点所在块排序，同一块内的按右端点的块排序，否则按时间排序。
值得一提的是，在修改的时候，由于我们的tim指针可能“往回跳”，所以我们要记下来之前的值，因此我们可以直接swap这俩值，回来的时候就直接swap回来。
最后一点就是块的大小，如果我们还像普通莫队那样，把块的大小直接设成$\sqrt{n}$，我们的时间复杂度会被卡成$O(n^2)$，因此有人证明了块大小为$\sqrt[3]{n^4t}$时最优(t为修改次数)，但是有一个更简单的设定大小方式，即把块的大小设为 $n^{\frac{2}{3}}$ ,这样的复杂度为 $O(n^{\frac{5}{3}})$。
1 //#pragma GCC optimize(3) 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #define N 1333340 8 using namespace std; 9 int read() 10 { 11 int x=0,f=1;char ch=getchar(); 12 while(ch<'0'||ch>'9')ch=getchar(); 13 while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} 14 return x*f; 15 } 16 struct query 17 { 18 int l,r,tim,x; 19 }q[N]; 20 struct modify 21 { 22 int pos,color; 23 }c[N]; 24 int n,m,cntq,cntc,l=1,r,tim,now,a[N],belong[N],siz,bnum,cnt[N],ans[N]; 25 char opt; 26 bool cmp(query a,query b) 27 { 28 return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.r]^belong[b.r])?belong[a.r]<belong[b.r]:(a.tim<b.tim)); 29 } 30 int main() 31 { 32 n=read();m=read(); 33 siz=pow(n,2.0/3.0); 34 bnum=ceil((double)(n/siz)); 35 for(int i=1;i<=bnum;i++) 36 { 37 for(int j=(i-1)*siz+1;j<=i*siz;j++) 38 { 39 belong[j]=i; 40 } 41 } 42 for(int i=1;i<=n;i++)a[i]=read(); 43 for(int i=1;i<=m;i++) 44 { 45 opt=getchar();getchar(); 46 if(opt=='Q') 47 { 48 q[++cntq].l=read(); 49 q[cntq].r=read(); 50 q[cntq].tim=cntc; 51 q[cntq].x=cntq; 52 } 53 else 54 { 55 c[++cntc].pos=read(); 56 c[cntc].color=read(); 57 } 58 } 59 sort(q+1,q+cntq+1,cmp); 60 for(int i=1;i<=cntq;i++) 61 { 62 int ll=q[i].l,rr=q[i].r,tt=q[i].tim; 63 while(l<ll)now-=!--cnt[a[l++]]; 64 while(l>ll)now+=!cnt[a[--l]]++; 65 while(r<rr)now+=!cnt[a[++r]]++; 66 while(r>rr)now-=!--cnt[a[r--]]; 67 while(tim<tt) 68 { 69 ++tim; 70 if(c[tim].pos>=ll&&c[tim].pos<=rr)now-=!--cnt[a[c[tim].pos]]-!cnt[c[tim].color]++; 71 swap(a[c[tim].pos],c[tim].color); 72 } 73 while(tim>tt) 74 { 75 if(c[tim].pos>=ll&&c[tim].pos<=rr)now-=!--cnt[a[c[tim].pos]]-!cnt[c[tim].color]++; 76 swap(a[c[tim].pos],c[tim].color); 77 --tim; 78 } 79 ans[q[i].x]=now; 80 } 81 for(int i=1;i<=cntq;i++)printf("%d\n",ans[i]); 82 return 0; 83 } View Code
转载于:https://www.cnblogs.com/szmssf/p/11547103.html
