分块 note

· · 个人记录

有一说一，分块写得太爽了

三倍经验：\ P3870\ P2864\ P2574

  len=sqrt(n);
    for(int i=1;i<=n;i++)
        id[i]=(i-1)/len+1;

这一步对数组划分的处理很精妙\ 后面的分区间暴力处理听着慢，写着快\ 整块快速溜，散块暴力处理\

O(n\sqrt n) 
void change(int l,int r){
    int st=id[l],ed=id[r],js=0;
    if(st==ed){
        for(int i=l;i<=r;i++){
            if(a[i]^b[st])js++;
            a[i]=a[i]^1;
        }
        s[st]+=(r-l+1-2*js);
    }else{
        for(int i=l;id[i]==st;i++){
            if(a[i]^b[st])js++;
            a[i]=a[i]^1;
        }
        s[st]+=(st*len-l+1-2*js);js=0;
        for(int i=st+1;i<ed;i++)b[i]=b[i]^1,s[i]=len-s[i];
        for(int i=r;id[i]==ed;i--){
            if(a[i]^b[ed])js++;
            a[i]=a[i]^1;
        }
        s[ed]+=(r-(ed-1)*len-2*js);
    }
}

这个是区间修改，这里懒标记永久化，且对散块的区间整体修改也不在循环中进行，两者大大加快了速度。\ 简述原理：\ 因为是对区间修，所以有关联性，如st=ed时，本区间内的 1 的个数记为 js ，先认为 l 到 r 都为 0 ，那么 s[st] 将加上 （r-l+1） ，然后因为原本 s[st] 有 js 个 1 ，然后这些 1 也变成了 0 ，所以 s[st] 应该要减去原本 1 的个数，再减去原本 1 变成 0 的个数，即得到：

s[st]+=(r-l+1-2*js);

记得因为懒标记未下传，而 js 要记录当前数组中 1 的个数，所以应该要拿数组值和懒标记异或后再判断，即：

if(a[i]^b[id[i]])js++;

整块的处理上因为单块中 0 和 1 的总数量为 len，所以处理时之间反转即可：

s[i]=len-s[i];

最后求和答案

int query(int l,int r){
    int st=id[l],ed=id[r],ans=0;
    if(st==ed){
        for(int i=l;i<=r;i++)ans=ans+(a[i]^b[st]);
    }else{
        for(int i=l;id[i]==st;i++)ans=ans+(a[i]^b[st]);
        for(int i=st+1;i<ed;i++)ans=ans+s[i];
        for(int i=r;id[i]==ed;i--)ans=ans+(a[i]^b[ed]);
    }
    return ans;
}

记得下传懒标记 # 送个板子题P2357 附送代码，同样做了 O(1) 块处理：

#include<bits/stdc++.h>
using namespace std;
long long n,q,id[200005],len,s[2005],a[200005],b[200005];
void change(int l,int r,long long k){
    int st=id[l],ed=id[r];
    long long ans=0;
    if(st==ed){
        for(int i=l;i<=r;i++)a[i]+=k;
        s[st]+=(r-l+1)*k;
    }else{
        for(int i=l;id[i]==st;i++)a[i]+=k;
        s[st]+=(st*len-l+1)*k;
        for(int i=st+1;i<ed;i++)b[i]+=k,s[i]+=len*k;
        for(int i=r;id[i]==ed;i--)a[i]+=k;
        s[ed]+=(r-(ed-1)*len)*k;
    }
}
long long query(int l,int r){
    int st=id[l],ed=id[r];
    long long ans=0;
    if(st==ed)
        for(int i=l;i<=r;i++)ans+=(a[i]+b[st]);
    else{
        for(int i=l;id[i]==st;i++)ans+=(a[i]+b[st]);
        for(int i=st+1;i<ed;i++)ans+=s[i];
        for(int i=r;id[i]==ed;i--)ans+=(a[i]+b[ed]);
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    len=sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        id[i]=(i-1)/len+1;
        s[id[i]]+=a[i];
    }
    for(long long i=1,x,l,r,k;i<=q;i++){
        cin>>x;
        if(x==1){
            cin>>l>>r>>k;
            change(l,r,k);
        }else if(x==2){
            cin>>k;
            change(1,1,k);
        }else if(x==3){
            cin>>k;
            change(1,1,-k);
        }else if(x==4){
            cin>>l>>r;
            cout<<query(l,r)<<'\n';
        }else cout<<(a[1]+b[1])<<'\n';
    }
    return 0;
}

建议先学线段树再来碰分块（有些线段树题可以用分块来做），便于理解懒标记