分块吼啊

## 学习笔记——分块

之前一直不会写分块。
咕到了今天终于写了几个裸题

LOJ数列分块入门1

区间加，单点查
线段树很容易，但是要练分块更容易
把数列分成\(\sqrt{n}\)的块
整块的打\(tag\)两边的暴力
代码如下:

#include<bits/stdc++.h>
using namespace std;
const int maxn=50010;
int n,a[maxn],t,L[maxn],R[maxn],bl[maxn],tag[maxn];
inline void add(int l,int r,int d){
    if(bl[l]==bl[r])
        for(int i=l;i<=r;i++) a[i]+=d;
    else{
        for(int i=bl[l]+1;i<=bl[r]-1;i++) tag[i]+=d;
        for(int i=l;i<=R[bl[l]];i++) a[i]+=d;
        for(int i=L[bl[r]];i<=r;i++) a[i]+=d;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    t=sqrt(n);
    for(int i=1;i<=t;i++){
        L[i]=(i-1)*t+1;R[i]=t*i;
    }
    if(R[t]<n) t++,L[t]=R[t-1]+1,R[t]=n;
    for(int i=1;i<=t;i++)
        for(int j=L[i];j<=R[i];j++) bl[j]=i;
    for(int i=1;i<=n;i++){
        int op,l,r,c;scanf("%d%d%d%d",&op,&l,&r,&c);
        if(op) printf("%d\n",a[r]+tag[bl[r]]);
        else add(l,r,c);
    }
    return 0;
}

LuoguP2801 教主的魔法

查大于等于\(c\)的数，可以转化为整体区间减去小于的数
小于\(c\)的数的个数就是排名
所以分块在块内查排名，暴力\(sort\)
左右暴力查多少个大的
我用\(vector\)开O2才A

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int t,n,q,a[maxn],bl[maxn],L[maxn],R[maxn],tg[maxn];
vector<int> rk[maxn];
inline void add(int l,int r,int d){
    if(bl[l]==bl[r]){
        for(int i=l;i<=r;i++) a[i]+=d;
        rk[bl[l]].clear();
        for(int i=L[bl[l]];i<=R[bl[l]];i++) rk[bl[l]].push_back(a[i]);
        sort(rk[bl[l]].begin(),rk[bl[l]].end());
    }else{
        for(int i=l;i<=R[bl[l]];i++) a[i]+=d;
        rk[bl[l]].clear();
        for(int i=L[bl[l]];i<=R[bl[l]];i++) rk[bl[l]].push_back(a[i]);
        sort(rk[bl[l]].begin(),rk[bl[l]].end());
        for(int i=bl[l]+1;i<=bl[r]-1;i++) tg[i]+=d;
        for(int i=L[bl[r]];i<=r;i++) a[i]+=d;
        rk[bl[r]].clear();
        for(int i=L[bl[r]];i<=R[bl[r]];i++) rk[bl[r]].push_back(a[i]);
        sort(rk[bl[r]].begin(),rk[bl[r]].end());
    }
}
inline int ask(int l,int r,int c){
    int ans=0;
    if(bl[l]==bl[r]){
        for(int i=l;i<=r;i++) if(tg[bl[l]]+a[i]>=c) ans++;
        return ans;
    }else{
        for(int i=l;i<=R[bl[l]];i++)
            if(tg[bl[l]]+a[i]>=c) ans++;
        for(int i=L[bl[r]];i<=r;i++)
            if(tg[bl[r]]+a[i]>=c) ans++;
        for(int i=bl[l]+1;i<=bl[r]-1;i++){
            int x=c-tg[i],res=0;
            res=lower_bound(rk[i].begin(),rk[i].end(),x)-rk[i].begin();
            ans+=(R[i]-L[i]+1)-res;
        }
        return ans;
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    t=sqrt(n);
    for(int i=1;i<=t;i++){
        L[i]=(i-1)*t+1;R[i]=i*t;
    }
    if(R[t]<n) t++,L[t]=R[t-1]+1,R[t]=n;
    for(int i=1;i<=t;i++) for(int j=L[i];j<=R[i];j++) bl[j]=i,rk[i].push_back(a[j]);
    for(int i=1;i<=t;i++) sort(rk[i].begin(),rk[i].end());
    while(q--){
        char op[5];scanf("%s",op);
        if(op[0]=='M'){
            int l,r,d;scanf("%d%d%d",&l,&r,&d);
            add(l,r,d);
        }else{
            int l,r,c;scanf("%d%d%d",&l,&r,&c);
            printf("%d\n",ask(l,r,c));
        }
    }
    return 0;
}

LuoguP3203 [HNOI2010]弹飞绵羊

LCT的题，用分块水
每个点记上\(sum\)表示跳出块需要几步，\(to\)表示跳出块到几号点
修改就改了自己块的前面的数就行
代码如下:

#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
int t,n,m,a[maxn],L[maxn],R[maxn],bl[maxn];
int to[maxn],sm[maxn];
inline int ask(int x){
    int ans=0;
    while(x<=n){
        ans+=sm[x];x=to[x];
    }
    return ans;
}
inline void change(int x,int d){
    a[x]=d;
    for(int i=x;i>=L[bl[x]];i--){
        if(i+a[i]>R[bl[x]]) sm[i]=1,to[i]=i+a[i];
        else sm[i]=sm[i+a[i]]+1,to[i]=to[i+a[i]];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    t=sqrt(n);
    for(int i=1;i<=t;i++){
        L[i]=(i-1)*t+1;R[i]=i*t;
    }
    if(R[t]!=n) t++,L[t]=R[t-1]+1,R[t]=n;
    for(int i=1;i<=t;i++) for(int j=L[i];j<=R[i];j++)
        bl[j]=i;
    for(int i=1;i<=n;i++)
        for(int j=R[i];j>=L[i];j--){
            if(j+a[j]>R[i])
                sm[j]=1,to[j]=j+a[j];
            else sm[j]=sm[j+a[j]]+1,to[j]=to[j+a[j]];
        }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int op;scanf("%d",&op);
        if(op==1){
            int x;scanf("%d",&x);x++;printf("%d\n",ask(x));
        }else{
            int x,y;scanf("%d%d",&x,&y);x++;
            change(x,y);
        }
    }
    return 0;
}