分塊與莫隊(duì)

莫隊(duì)只學(xué)了不同，帶修和回滾。 我太菜

分塊九講：

推博：「分塊」數(shù)列分塊入門1 – 9 by hzwer

代碼直接看 loj

1. 數(shù)列分塊入門 2

   對(duì)于塊內(nèi)排序即可。

2. 數(shù)列分塊入門 3

   也是排序。

   不同的是可以用 set 維護(hù)，比較方便。

3. 數(shù)列分塊入門 4

   同線段樹，寫 tag 就行了。

4. 數(shù)列分塊入門 5

   考慮開很少次根號(hào)就會(huì)都變 \(1\)，維護(hù)區(qū)間和，區(qū)間是否都為一，暴力對(duì)不為一的修改。

5. 數(shù)列分塊入門 6

   其實(shí)本題不隨機(jī)。

   直接分塊插入。

   在不隨機(jī)數(shù)據(jù)下可以重構(gòu)分塊。

6. 數(shù)列分塊入門 7

   同線段樹，注意 tag 轉(zhuǎn)移順序。

   考慮 \((a+b)c=ac+bc\) 所以乘的時(shí)候也乘一下加法 tag，最后先乘在加。

7. 數(shù)列分塊入門 8

   類似區(qū)間根號(hào)，判斷區(qū)間是否全相等即可。

   也可以珂朵莉

8. 數(shù)列分塊入門 9（蒲公英）

   分塊：

   類似HH的項(xiàng)鏈等題。

   整塊預(yù)處理出 \(a\) 塊到 \(b\) 塊眾數(shù)和數(shù)出現(xiàn)次數(shù)。

   眾數(shù)直接預(yù)處理，數(shù)出現(xiàn)次數(shù)可以用數(shù)的位置二分，也可以前綴和。（雖然二分多 log 但是實(shí)測(cè)二分更快）

   散塊直接暴力求和，因?yàn)橹挥猩K出現(xiàn)的數(shù)才有可能更新眾數(shù)。

   注意塊大小不是 \(\sqrt n\)

   莫隊(duì)：

   離線

   回滾板子，加數(shù)比減數(shù)好維護(hù)。

其他：

1. Bounce 彈飛綿羊

   在同一塊內(nèi)路徑壓縮。

   就可以將單次修改和查詢整成根號(hào)

   CODE

   #include<bits/stdc++.h>
   using namespace std;
   typedef long long llt;
   typedef unsigned long long ull;
   #define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
   #define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
   const int N=2e5+4,S=1e3+3;
   int n,m;
   
   namespace IO{
       template<typename T> inline void write(T x){
           static T st[45];T top=0;if(x<0)x=~x+1,putchar('-');
           do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48);
       }
       template<typename T> inline void read(T &x){
           char s=getchar();x=0;bool pd=false;while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
           while('0'<=s&&s<='9'){x=(x<<1)+(x<<3)+(s^48),s=getchar();}if(pd) x=-x;
       }
   }
   namespace IO{
       template<typename T,typename... Args> inline void read(T& x,Args&... args){read(x);read(args...);}
       inline void write(const char c){putchar(c);}
       inline void write(const char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
       template<typename T> inline void Write(T x){write(x);putchar(' ');}
       inline void Write(const char c){write(c);if(c!='\n') putchar(' ');}
       inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
       template<typename T,typename... Args> inline void write(T x,Args... args){write(x);write(args...);}
       template<typename T,typename... Args> inline void Write(T x,Args... args){Write(x);Write(args...);}
   }
   using namespace IO;
   class DB{
   private:
       int val[N],to[N],cst[N],pos[N],bg[S],ed[S],len;
   public:
       inline void Update(int id){
           For_(j,ed[id],bg[id],1){
               to[j]=val[j]+j;cst[j]=1;
               if(to[j]<=ed[id]) cst[j]+=cst[to[j]],to[j]=to[to[j]];
               // cout<<j<<' '<<to[j]<<' '<<cst[j]<<endl;
           }
       }
       inline void Init(int n){
           len=sqrt(n);
           For(i,1,n,1){
               int p=pos[i]=(i-1)/len+1;
               if(!bg[p]) bg[p]=i; ed[p]=i;
               read(val[i]),to[i]=val[i];
           }
           For(i,1,pos[n],1) Update(i);
       }
       inline void Add(int x,int t){val[x]=t,Update(pos[x]);}
       inline int Get(int x){
           int cnt=0;
           while(x<=n) cnt+=cst[x],x=to[x];
           return cnt;
       }
   }db;
   
   int main(){
   #ifndef ONLINE_JUDGE
       freopen("in_out/in.in","r",stdin);
       freopen("in_out/out.out","w",stdout);
   #endif
       read(n),db.Init(n);
       read(m);
       For(i,1,m,1){
           int opt,x,t;read(opt,x); x++;
           if(opt==1) write(db.Get(x),'\n');
           else read(t),db.Add(x,t);
       }
   }
   

2. 數(shù)顏色

   分塊：

   修改不多于 \(1000\)，所以類似分塊 9 暴力修改即可。

   CODE

   #include<bits/stdc++.h>
   using namespace std;
   typedef long long llt;
   typedef unsigned long long ull;
   #define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
   #define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
   const int N=5e4+4,S=1e3+2,M=1e6+4;
   int n,m;
   
   namespace IO{
       template<typename T> inline void write(T x){
           static T st[45];T top=0;if(x<0)x=~x+1,putchar('-');
           do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48);
       }
       template<typename T> inline void read(T &x){
           char s=getchar();x=0;bool pd=false;while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
           while('0'<=s&&s<='9'){x=(x<<1)+(x<<3)+(s^48),s=getchar();}if(pd) x=-x;
       }
   }
   namespace IO{
       template<typename T,typename... Args> inline void read(T& x,Args&... args){read(x);read(args...);}
       inline void write(const char c){putchar(c);}
       inline void write(const char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
       template<typename T> inline void Write(T x){write(x);putchar(' ');}
       inline void Write(const char c){write(c);if(c!='\n') putchar(' ');}
       inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
       template<typename T,typename... Args> inline void write(T x,Args... args){write(x);write(args...);}
       template<typename T,typename... Args> inline void Write(T x,Args... args){Write(x);Write(args...);}
   }
   using namespace IO;
   class DB{
   private:
       int a[N],to[M],pos[N],bg[S],ed[S],qs[S][N],tt[S][S],len,tot;
       bool cnt[N];
       queue<int> que;
   public:
       inline void init(int n){
           len=sqrt(n);
           For(i,1,n,1){
               int p=pos[i]=(i-1)/len+1,x; read(x);
               if(!bg[p]) bg[p]=i; ed[p]=i;
               if(to[x]) a[i]=to[x];
               else a[i]=to[x]=++tot;
           }// init
           For(i,1,pos[n],1){
               For(j,1,n,1) qs[i][j]=qs[i-1][j];
               For(j,bg[i],ed[i],1) qs[i][a[j]]++;
               For(j,i,pos[n],1){
                   tt[i][j]=tt[i][j-1];
                   For(k,bg[j],ed[j],1)
                       if(!cnt[a[k]]) tt[i][j]++,cnt[a[k]]=1;
               }
               memset(cnt,0,sizeof cnt);
           }// qs & tt
       }
       #define check(l,r,t) (qs[r][t]-qs[l][t])
       inline int Get(int l,int r){
           int L=pos[l],R=pos[r],ans=0;
           if(L==R)
               For(i,l,r,1) {if(!cnt[a[i]]) ans++,cnt[a[i]]=1,que.push(a[i]);}
           else{
               ans=tt[L+1][R-1];
               For(i,l,ed[L],1) if(!cnt[a[i]]&&!check(R-1,L,a[i])) ans++,cnt[a[i]]=1,que.push(a[i]);
               For(i,bg[R],r,1) if(!cnt[a[i]]&&!check(R-1,L,a[i])) ans++,cnt[a[i]]=1,que.push(a[i]);
           }
           while(!que.empty()) cnt[que.front()]=0,que.pop();
           return ans;
       }
       inline void Upd(int x,int t){
           if(!to[t]) to[t]=++tot; t=to[t];
           int P=pos[x],nw=a[x]; a[x]=t;
           For(i,P,pos[n],1) qs[i][nw]--;
           For(i,1,P,1) For(j,P,pos[n],1) if(!check(i-1,j,nw)) tt[i][j]--;
           For(i,P,pos[n],1) qs[i][t]++;
           For(i,1,P,1) For(j,P,pos[n],1) if(check(i-1,j,t)==1) tt[i][j]++;
       }
       #undef check
   }db;
   
   int main(){
   #ifndef ONLINE_JUDGE
       freopen("in_out/in.in","r",stdin);
       freopen("in_out/out.out","w",stdout);
   #endif
       read(n,m);db.init(n);
       For(i,1,m,1){
           char opt;scanf(" %c",&opt);
           int l,r;read(l,r);
           if(opt=='Q') write(db.Get(l,r),'\n');
           else db.Upd(l,r);
       }
   }
   

   莫隊(duì)：

   帶修板子，多一維時(shí)間。

   CODE

   #include<bits/stdc++.h>
   using namespace std;
   typedef long long llt;
   typedef unsigned long long ull;
   #define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
   #define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
   const int N=5e4+3,R=1e6+4;
   
   namespace IO{
       int READ_NONPARAMETRIC_INIT;
       template<typename T> inline void write(T x){
           static T st[45];T top=0;if(x<0)x=~x+1,putchar('-');
           do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48);
       }
       template<typename T> inline T read(T &x=READ_NONPARAMETRIC_INIT){
           char s=getchar();x=0;bool pd=false;while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
           while('0'<=s&&s<='9'){x=(x<<1)+(x<<3)+(s^48),s=getchar();}if(pd) x=-x; return x;
       }
   }
   namespace IO{
       template<typename T,typename... Args> inline void read(T& x,Args&... args){read(x);read(args...);}
       inline void write(const char c){putchar(c);}
       inline void write(const char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
       template<typename T> inline void Write(T x){write(x);putchar(' ');}
       inline void Write(const char c){write(c);if(c!='\n') putchar(' ');}
       inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
       template<typename T,typename... Args> inline void write(T x,Args... args){write(x);write(args...);}
       template<typename T,typename... Args> inline void Write(T x,Args... args){Write(x);Write(args...);}
   }
   using namespace IO;
   namespace MD{
       int pos[N],ed[N],val[N],ans[N],cnt[R],n,m,Len,qtot,rtot,cas;
       struct Q{
           int l,r,t,id;
           inline void Rd(int a,int b){read(l,r),t=a,id=b;}
           bool operator<(Q b){return (pos[l]^pos[b.l])?pos[l]<pos[b.l]:((pos[r]^pos[b.r])?pos[r]<pos[b.r]:t<b.t);}
       }cq[N];
       struct R{
           int p,val;
           inline void Rd(){read(p,val);}
       }cr[N];
       inline void Ins(int x){cas+=!cnt[x]++;}
       inline void Del(int x){cas-=!--cnt[x];}
       inline void Mdf(int t,int l,int r){
           int p=cr[t].p;
           if(l<=p&&p<=r) Del(val[p]),Ins(cr[t].val);
           swap(val[p],cr[t].val);
       }
       inline void Init(){
           read(n,m);Len=pow(n,2.0/3.0);
           For(i,1,n,1) pos[i]=(i-1)/Len+1,ed[pos[i]]=i,read(val[i]);
           For(i,1,m,1){
               char x;scanf(" %c",&x);
               if(x=='Q') cq[++qtot].Rd(rtot,qtot);
               else cr[++rtot].Rd();
           }
           sort(cq+1,cq+qtot+1);
       }
       inline void Solve(){
           int l=1,r=0,t=0;
           For(i,1,qtot,1){
               int ql=cq[i].l,qr=cq[i].r,qt=cq[i].t,id=cq[i].id;
               while(l<ql) Del(val[l++]);
               while(l>ql) Ins(val[--l]);
               while(r<qr) Ins(val[++r]);
               while(r>qr) Del(val[r--]);
               while(t<qt) Mdf(++t,ql,qr);
               while(t>qt) Mdf(t--,ql,qr);
               ans[id]=cas;
           }
           For(i,1,qtot,1) write(ans[i],'\n');
       }
   }
   int main(){
   #ifndef ONLINE_JUDGE
       freopen("in_out/in.in","r",stdin);
       freopen("in_out/out.out","w",stdout);
   #endif
       MD::Init(),MD::Solve();
   }
   

3. 顏色

   分別維護(hù) \(a\) 塊到 \(b\) 塊數(shù)量前綴和和平方前綴和。

   散塊算貢獻(xiàn)即可。

   CODE

   #include<bits/stdc++.h>
   using namespace std;
   typedef long long llt;
   typedef unsigned long long ull;
   #define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
   #define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
   #define ing long long
   const int N=5e4,S=40,M=2e4;
   int n,m,q;
   llt ans;
   
   namespace IO{
       template<typename T> inline void write(T x){
           static T st[45];T top=0;if(x<0)x=~x+1,putchar('-');
           do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48);
       }
       template<typename T> inline void read(T &x){
           char s=getchar();x=0;bool pd=false;while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
           while('0'<=s&&s<='9'){x=(x<<1)+(x<<3)+(s^48),s=getchar();}if(pd) x=-x;
       }
   }
   namespace IO{
       template<typename T,typename... Args> inline void read(T& x,Args&... args){read(x);read(args...);}
       inline void write(const char c){putchar(c);}
       inline void write(const char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
       template<typename T> inline void Write(T x){write(x);putchar(' ');}
       inline void Write(const char c){write(c);if(c!='\n') putchar(' ');}
       inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
       template<typename T,typename... Args> inline void write(T x,Args... args){write(x);write(args...);}
       template<typename T,typename... Args> inline void Write(T x,Args... args){Write(x);Write(args...);}
   }
   using namespace IO;
   class DB{
   private:
       int val[N],pos[N],bg[S],ed[S],Len;
       llt qf[S][S][M],s[S][M],cnt[M];
   public:
       inline llt Sum(int L,int R,int k){if(L>R) return 0;return s[R][k]-s[L-1][k];}
       inline llt Pow(llt a){return a*a;}
       inline void Init(int n,int m){
           Len=pow(n,2.0/3);
           For(i,1,n,1){
               int p=pos[i]=(i-1)/Len+1;
               if(!bg[p]) bg[p]=i; ed[p]=i;
               read(val[i]);
           }
           For(i,1,pos[n],1){
               For(j,1,m,1) s[i][j]=s[i-1][j];
               For(j,bg[i],ed[i],1) s[i][val[j]]++;
           }
           For(i,1,pos[n],1) For(j,i,pos[n],1){
               For(k,1,m,1) qf[i][j][k]=Pow(Sum(i,j,k));
               For(k,1,m,1) qf[i][j][k]+=qf[i][j][k-1];
           }
       }
       inline llt Get(int l,int r,int a,int b){
           int L=pos[l],R=pos[r];
           llt ans=0;
           if(L==R){
               For(i,l,r,1) if(a<=val[i]&&val[i]<=b) cnt[val[i]]++;
               For(i,l,r,1) if(cnt[val[i]]) ans+=Pow(cnt[val[i]]),cnt[val[i]]=0;  
           }else{
               ans+=(qf[L+1][R-1][b]-qf[L+1][R-1][a-1]);
               For(i,l,ed[L],1) if(a<=val[i]&&val[i]<=b) cnt[val[i]]++;
               For(i,bg[R],r,1) if(a<=val[i]&&val[i]<=b) cnt[val[i]]++;
               For(i,l,ed[L],1)
                   if(cnt[val[i]]) ans+=(Pow(cnt[val[i]]+Sum(L+1,R-1,val[i]))-Pow(Sum(L+1,R-1,val[i]))),cnt[val[i]]=0;
               For(i,bg[R],r,1)
                   if(cnt[val[i]]) ans+=(Pow(cnt[val[i]]+Sum(L+1,R-1,val[i]))-Pow(Sum(L+1,R-1,val[i]))),cnt[val[i]]=0;
           }
           return ans;
       }
   }db;
   
   signed main(){
   #ifndef ONLINE_JUDGE
       freopen("in_out/in.in","r",stdin);
       freopen("in_out/out.out","w",stdout);
   #endif
       read(n,m,q); db.Init(n,m);
       For(i,1,q,1){
           int l,r,a,b;read(l,r,a,b);
           l^=ans,r^=ans,a^=ans,b^=ans;
           write(ans=db.Get(l,r,a,b),'\n');
       }
   }
   
   

4. 作業(yè)

   莫隊(duì)套值域分塊。

   第一問顯然，第二問值域分塊維護(hù)一下莫隊(duì)的移動(dòng)。

   CODE

   #include<bits/stdc++.h>
   using namespace std;
   typedef long long llt;
   typedef unsigned long long ull;
   #define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
   #define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
   const int N=1e6+4,M=1e6+4;
   int n,m;
   
   namespace IO{
       int READ_NONPARAMETRIC_INIT;
       template<typename T> inline void write(T x){
           static T st[45];T top=0;if(x<0)x=~x+1,putchar('-');
           do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48);
       }
       template<typename T> inline T read(T &x=READ_NONPARAMETRIC_INIT){
           char s=getchar();x=0;bool pd=false;while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
           while('0'<=s&&s<='9'){x=(x<<1)+(x<<3)+(s^48),s=getchar();}if(pd) x=-x; return x;
       }
   }
   namespace IO{
       template<typename T,typename... Args> inline void read(T& x,Args&... args){read(x);read(args...);}
       inline void write(const char c){putchar(c);}
       inline void write(const char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
       template<typename T> inline void Write(T x){write(x);putchar(' ');}
       inline void Write(const char c){write(c);if(c!='\n') putchar(' ');}
       inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
       template<typename T,typename... Args> inline void write(T x,Args... args){write(x);write(args...);}
       template<typename T,typename... Args> inline void Write(T x,Args... args){Write(x);Write(args...);}
   }
   using namespace IO;
   class DB{
   private:
       static const int S=1e3+3;
       int val[N],pos[N],sum[S],bg[S],ed[S],Len=1000;
   public:
       DB(){For(i,1,N-2,1){int p=pos[i]=(i-1)/Len+1; if(!bg[p]) bg[p]=i; ed[p]=i;}}
       inline void Add(int x,int t){val[x]+=t,sum[pos[x]]+=t;}
       inline bool Empty(int x){return val[x]==0;}
       inline int Sum(int l,int r){
           int L=pos[l],R=pos[r],ans=0;
           if(L==R) For(i,l,r,1) ans+=val[i];
           else{
               For(i,l,ed[L],1) ans+=val[i];
               For(i,bg[R],r,1) ans+=val[i];
               For(i,L+1,R-1,1) ans+=sum[i];
           }
           return ans;
       }
   }kd,sm;
   namespace MD{
       int pos[N],val[N],Len;
       pair<int,int> ans[M];
       struct Q{
           int l,r,a,b,id;
           inline void Rd(int x){read(l,r,a,b),id=x;} 
           bool operator<(Q x){return (pos[l]^pos[x.l])?pos[l]<pos[x.l]:((pos[l]&1)?r>x.r:r<x.r);}
       }qst[N];
       inline void Init(int n,int m){
           Len=sqrt(n);
           For(i,1,n,1) pos[i]=(i-1)/Len+1,read(val[i]);
           For(i,1,m,1) qst[i].Rd(i);
           sort(qst+1,qst+m+1);
       }
       inline void ins(int x){sm.Add(val[x],1);if(kd.Empty(val[x])) kd.Add(val[x],1);}
       inline void del(int x){sm.Add(val[x],-1);if(sm.Empty(val[x])) kd.Add(val[x],-1);}
       inline void Solve(){
           int l=1,r=0;
           For(i,1,m,1){
               int ql=qst[i].l,qr=qst[i].r,a=qst[i].a,b=qst[i].b,id=qst[i].id;
               while(l>ql) ins(--l);
               while(r<qr) ins(++r);
               while(l<ql) del(l++);
               while(r>qr) del(r--);
               ans[id]={sm.Sum(a,b),kd.Sum(a,b)};
           }
           For(i,1,m,1) Write(ans[i].first,ans[i].second,'\n');
       }
   }
   
   int main(){
   #ifndef ONLINE_JUDGE
       freopen("in_out/in.in","r",stdin);
       freopen("in_out/out.out","w",stdout);
   #endif
       read(n,m),MD::Init(n,m);
       MD::Solve();
   }