题解 CF896E 【Welcome home, Chtholly】

· · 题解

update:修改了一个错误。

第二分块。

其实这个题还是相对好想的，也比较简单（个人认为是大分块系列最简答的题）。

做 Ynoi 的题首先看数据范围和时空限制。

在 CF 上这个题不卡空间，但有一个加强版（见P4117）只有 62.5 MB 的空间且数据范围有 5 倍。因此我们需要优化。

而分块最好的空间优化方式是割开来一块一块处理，这样能将空间优化到线性。

但这也就要求块与块之间是独立的，并且块内修改查询总复杂度必须都是 \operatorname{O}(m) 的 ，才可以满足我们的要求（这其实可以看成一个提示）。

由于块的值域与 n 同阶，我们可以考虑利用这个值域（其实这又是一个提示）。

我们考虑这个块内部的最大值。不妨将其设置为 mx，并设置一个区间减的 tag（因为我们只会将数值减小而不会增大）。

如果 mx\le x\times 2，则我们直接把所有大于 x 的数减去 x。

如果 mx>x\times 2，则我们把小于 x 的数加上 x，并打上区间减的标记。

然后最大值随之更新即可。

这样我们发现，由于最大值与 n 同阶，因此一个块内的总复杂度是 \operatorname{O}(n)。

然后我们考虑怎么维护每个数的值。一开始我想到的方法是用一个链表来维护，维护每个值，碰到合并直接接到尾部。

后来参考了一下出题人题解（出题人给出了 3 中写法），发现那个并查集最好写。

具体的方法是，对每个值开一个并查集，然后记录这个并查集的 size。

修改的时候直接合并两个值的并查集，查询的时候直接输出这个并查集的 size。

如果是零散块修改，就直接重构；零散块查询，就通过并查集找到范围内每个数的值，暴力统计即可。

#include <bits/stdc++.h>
#define rg register
#define il inline
using namespace std;
inline int read(){
    register int x=0;
    register bool f=0;
    register char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }
    return f?-x:x;
}
char cr[200];int tt;
inline void print(register int x,register char k='\n') {
    if(!x) putchar('0');
    if(x < 0) putchar('-'),x=-x;
    while(x) cr[++tt]=x%10+'0',x/=10;
    while(tt) putchar(cr[tt--]);
    putchar(k);
}
const int maxn=500050;
struct node{
    int l,r,opt,x;
}q[maxn];
int ans[maxn],n,m,fa[maxn],rt[maxn],cnt[maxn],d[maxn];
int L[maxn],R[maxn],lsh[maxn],tot,a[maxn],bl;
int mx,tag,l,r,tmp,ql,qr,x;
il int find(rg int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
il void merge(rg int x,rg int y){
    if(rt[y]){
        fa[rt[x]]=rt[y];
    }
    else{
        rt[y]=rt[x];    
        lsh[rt[y]]=y;
    }
    cnt[y]+=cnt[x];
    rt[x]=cnt[x]=0;
}
il void build(){
    mx=tag=tot=0;
    memset(rt,0,sizeof(rt));
    memset(cnt,0,sizeof(cnt));
    for(rg int i=l;i<=r;i++){
        mx=max(mx,a[i]);
        if(rt[a[i]])fa[i]=rt[a[i]];
        else{
            rt[a[i]]=fa[i]=i;
            lsh[i]=a[i];
        }
        cnt[a[i]]++;
    }
}
il void modify(){
    if((x<<1)<=mx-tag){
        for(int j=tag+1;j<=tag+x;j++) 
            if(rt[j]) merge(j,j+x);
        tag+=x;
    }
    else{
        for(int j=mx;j>tag+x;j--) 
            if(rt[j]) merge(j,j-x);
        if(tag+x<mx) mx=tag+x;
    }
}
void rebuild(){
    for(rg int j=l;j<=r;j++){
        a[j]=lsh[find(j)];
        rt[a[j]]=cnt[a[j]]=0;
        a[j]-=tag;
    }
    for(int j=l-10;j<=r+10;j++) lsh[j]=0;
    tag=mx=tot=0;
    tmp=min(qr,r);
    for(rg int j=max(ql,l);j<=tmp;j++){
        a[j]=a[j]>x?a[j]-x:a[j];
    }
    for(rg int j=l;j<=r;j++){
        mx=max(mx,a[j]);
        if(rt[a[j]])fa[j]=rt[a[j]];
        else{
            rt[a[j]]=fa[j]=j;
            lsh[j]=a[j];
        }
        cnt[a[j]]++;
    }
}
void get(rg int i){
    if(x+tag>500000) return;
    if(ql<=l&&r<=qr) ans[i]+=cnt[x+tag];
    else{
        tmp=min(r,qr);
        for(int j=max(l,ql);j<=tmp;j++)
            if(lsh[find(j)]==tag+x) ans[i]++;
    }
}
signed main(){
    n=read();m=read();bl=sqrt(n-1)+1;
    for(rg int i=1;i<=n;i++){
        a[i]=read();
    }
    for(rg int i=1;i<=m;i++){
        q[i].opt=read();
        q[i].l=read();
        q[i].r=read();
        q[i].x=read();
    }
    int lxl=1;
    L[1]=1;
    while(L[lxl]+bl<n){
        R[lxl]=L[lxl]+bl-1;
        lxl++;
        L[lxl]=R[lxl-1]+1;
    }
    R[lxl]=n;
    for(rg int srz=1;srz<=lxl;srz++){
        l=L[srz],r=R[srz];
        build();
        for(rg int i=1;i<=m;i++){
            ql=q[i].l,qr=q[i].r,x=q[i].x;
            if(r<ql||qr<l) continue;
            if(q[i].opt^2){
                if(ql<=l&&r<=qr){
                    modify();
                }
                else{
                    rebuild();
                }
            }
            else{
                get(i);
            }
        }
    }
    for(rg int i=1;i<=m;i++) 
        if(q[i].opt==2) print(ans[i]);
    return 0;
}