P4117 五彩斑斓的世界

题面

原题链接 click

题解

第二分块。
先不管 \(64\mathrm{MiB}\) 的空间限制，考虑分块，修改时散块暴力，整块考虑并查集维护哪些数变为了相同数，均摊分析一下时间复杂度 \(O((m+V)\sqrt n)\) 是能接受的。
然后是空间的问题，注意到块与块之间互不干扰，可以逐块处理，空间复杂度线性。

Code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2000000,MAXM=1000000,MAXC=200010;
class uset{
    private:
    int f[MAXC+5],s[MAXC+5];
    public:
    void init(){
        for(int i=0;i<=MAXC;i++){
            f[i]=i;
            s[i]=0;
        }
    }
    void upd(int x,int v=1,int exit_code=1){//值为x的数数量+v
        if(f[x]!=x) exit(exit_code);
        s[x]+=v;
    }
    uset(){
        init();
    }
    int fa(int x){
        if(f[x]==x) return x;
        return f[x]=fa(f[x]);
    }
    void unite(int x,int y){//x->y
        if(x!=f[x]) exit(2);
        if(y!=f[y]) exit(4);
//      y=fa(y);
        if(x==y) return;
        s[y]+=s[x]; s[x]=0;
        f[x]=y;
    }
    int operator[](const int d)const{
        return s[d];
    }
};
uset k;
int a[MAXN+5];
struct qry{
    int tp,l,r,x;
};
qry t[MAXM+5];
qry s[MAXM+5];
int T,len,m,n;
int b[3005],tag;
int d[MAXN+5];
int ans[MAXM+5],q;
void cg(){//保留tag
    for(int i=1;i<=len;i++){
        b[i]=k.fa(b[i]);
    }
}
void work(int l,int r){
    tag=0;
    k.init();
    int mx=-1;
    for(int i=1;i<=m;i++){
        s[i]={t[i].tp,max(l,t[i].l)-l+1,min(r,t[i].r)-l+1,t[i].x};
    }
    int LXL=0;
    for(int i=1;i<=len;i++){
        k.upd(b[i]);
        mx=max(mx,b[i]);
        LXL+=!b[i];
    }
    int lxl=mx;
    int cnt=0;
//  cout<<"*\n";
    for(int i=1;i<=m;i++){
//      for(int i=0;i<=lxl;i++) if(k.fa(i)==i) cout<<i<<' '; cout<<' '<<'\t'<<tag<<' '<<mx<<'\n';
        int type=s[i].tp,l=s[i].l,r=s[i].r,x=s[i].x;
        if(l>r){//无关 
//          cout<<"1";
            if(type==1){
                continue;
            }else{
                cnt++;
                continue;
            }
        }
//      cout<<type<<' '<<l<<' '<<r<<' '<<x<<'\n';
        if(r-l+1==len){//全局操作 
            if(type==1){//全局修改 
                if(x==0) continue;
//              cout<<"2";
                if(x+x>mx){
                    for(int i=x+1+tag;i<=mx+tag;i++){
                        k.unite(i,i-x);
                    }
                    mx=min(mx,x);
                }else{
                    for(int i=1+tag;i<=x+tag;i++){
                        k.unite(i,i+x);
                    }
                    mx-=x;
                    tag+=x;
                }
            }else{//全局查询 
//              cout<<"3";
                if(x==0) ans[++cnt]+=LXL;
                else ans[++cnt]+=k[x+tag];
            }
        }else{//局部操作（暴力） 
            cg();//真实值=b[i]-tag
            if(type==1){//局部修改 
//              cout<<"4";
                if(x==0) continue;
                for(int i=l;i<=r;i++) if(b[i]-tag>x){
                    k.upd(b[i],-1,133);
                    b[i]-=x; 
                    k.upd(b[i],1,233);
                }
            }else{//局部查询 
//              cout<<"5";
                int tot=0;
                if(x==0){
                    for(int i=l;i<=r;i++) if(b[i]==tag) tot++;
                }else{
                    for(int i=l;i<=r;i++){
                        if(b[i]-tag==x) tot++;
                    }
                }
                ans[++cnt]+=tot;
            }
        }
    }
    if(cnt!=q) exit(3);
}
signed main(){
//  freopen("P4117_1.in","r",stdin);
//  freopen("P4117_1.out","w",stdout);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    T=sqrt(n);
    for(int i=1;i<=n;i++){
        d[i]=(i+T-1)/T;
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>t[i].tp>>t[i].l>>t[i].r>>t[i].x;
        if(t[i].tp==2) q++;
    }
    int pos=1;
    for(int i=1;i<=d[n];i++){
//      cout<<"第"<<i<<"块：\n";
        memset(b,0,sizeof(b)); len=0;
        while(d[pos]==i){
            b[++len]=a[pos++];
        }
        work(pos-len,pos-1);
    }
    for(int i=1;i<=q;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}