题解：P4117 [Ynoi2018] 五彩斑斓的世界

· · 题解

第二分块。

题意

给定一个长度为 n 的序列 a ，有 m 次操作，共有两种：

1.将 a 的区间 [l,r] 内大于 x 的数减去 x。
2.查询 a 的区间 [l,r] 中 x 出现的次数。

## 做法 将序列分块，设块长为 $\sqrt n$，对于每个块记录最大值上界 $mx$。 考虑整块操作，因为每个位置的修改后的值只和修改前的值有关，所以我们可以对于每个块内，用并查集维护数值相同的位置，且额外维护每个数值对应并查集中集合的根，然后分两种情况讨论： - $mx\le2\times x

对于值域 (x,mx]，将并查集中这些值对应的集合向 -x 后的集合合并，此时 mx 减少为 x。

注意到每次给 mx 减少的值和做出实际操作的值数量是只相差常数的，所以这个部分的时间复杂度复杂度可以均摊为 O(V\sqrt n)。

对于散块修改，直接把整块重构然后暴力改掉；对于整块查询，出现次数就是 x 在当前块并查集中所对应的集合大小；对于散块查询，我们在并查集中额外维护每个联通块对应的数值即可。

如果按照一般方式开空间，空间复杂度为 O(V\sqrt n)，显然不可接受；观察到修改和查询时每块独立，因此离线下来逐块处理即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define max(...) max({__VA_ARGS__})
#define min(...) min({__VA_ARGS__})
#define tomx(x,...) ((x)=max((x),__VA_ARGS__))
#define tomn(x,...) ((x)=min((x),__VA_ARGS__))
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define N 2000005
#define V 100005
#define M 1000005
#define len 660
bool op[M];
int L[M],R[M],X[M],ans[M],rt[V],tag,mx,cnt[V];
int n,q;
int a[N];
struct node{
    int fa,v;
}d[N];
int find(int u){
    for(;u^d[u].fa;) u=d[u].fa=d[d[u].fa].fa;
    return u;
}
void merge(int x,int y){
    //x->y
    if(!rt[y]){
        rt[y]=rt[x];
        d[rt[y]].v=y;
    }else{
        d[rt[x]].fa=rt[y];
    }
    rt[x]=0;
    cnt[y]+=exchange(cnt[x],0);
}
void solve(int id){
    int lp=(id-1)*len+1;
    int rp=id*len;
    tomn(rp,n);
    mx=tag=0;
    rep(i,lp,rp){
        tomx(mx,a[i]);
        if(!rt[a[i]]) rt[a[i]]=d[i].fa=i,d[i].v=a[i];
        else d[i].fa=rt[a[i]];
        cnt[a[i]]++;
    }
    rep(iq,1,q){
        int l=L[iq],r=R[iq],x=X[iq];
        if(r<lp||rp<l) continue;
        if(l<=lp&&rp<=r){
            if(!op[iq]){
                if(!x) continue;
                if(mx-tag<=2*x){
                    rep(i,x+1+tag,mx){
                        if(rt[i]) merge(i,i-x);
                    }
                    tomn(mx,x+tag);
                }else{
                    per(i,x+tag,0+tag){
                        if(rt[i]) merge(i,i+x);
                    }
                    tag+=x;
                }
            }else{
                if(x+tag<V) ans[iq]+=cnt[x+tag];
            }
        }else{
            if(!op[iq]){
                if(!x) continue;
                rep(i,lp,rp) a[i]=d[find(i)].v;
                rep(i,lp,rp) rt[a[i]]=cnt[a[i]]=0;
                rep(i,lp,rp) a[i]-=tag;
                rep(i,lp,rp) d[i].v=0;
                rep(i,max(l,lp),min(r,rp)) a[i]-=x&-(a[i]>x);
                mx=tag=0;
                rep(i,lp,rp){
                    tomx(mx,a[i]);
                    if(!rt[a[i]]) rt[a[i]]=d[i].fa=i,d[i].v=a[i];
                    else d[i].fa=rt[a[i]];
                    cnt[a[i]]++;
                }
            }else{
                if(x+tag<V) rep(i,max(l,lp),min(r,rp)) ans[iq]+=(d[find(i)].v-tag==x);
            }
        }
    }
    rep(i,lp,rp) a[i]=d[find(i)].v,rt[a[i]]=cnt[a[i]]=0;
}
main(){
#ifdef LOCAL
    auto start=clock();
#endif
    ios::sync_with_stdio(0),cin.tie(nullptr);
    cin>>n>>q;
    rep(i,1,n) cin>>a[i];
    rep(i,1,q){
        int c;
        cin>>c>>L[i]>>R[i]>>X[i];
        op[i]=c-1;
    }
    rep(i,1,(n-1)/len+1) solve(i);
    rep(i,1,q){
        if(op[i]) cout<<ans[i]<<"\n";
    }
#ifdef LOCAL
    clog<<"\ntime: "<<clock()-start<<" ms\n";
#endif
}