发布时间：2024-07-31

分块

维护块内信息，一般块长选取 $ \sqrt n $
如果是区间查询，如果在完整的块中，直接暴力
不完整，拆分成左边不完整，中间若干个完整，右边不完整
时间复杂度: $ O(\sqrt n) $ 模板M L R C,对区间加C
A L R C,查询区间大于等于C的个数

cpp

int e[N];//数组副本
int L[N],R[N];//L[i],R[i]表示编号为i的左右边界
int be[N];//be[i]表示i属于第几块
int a[N];
int tot,tag[N];//tag为信息
void solve(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    auto cal=[&](int k){//重构第k个块
        for(int i=L[k];i<=R[k];i++)e[i]=a[i];
        sort(e+L[k],e+R[k]+1);
    };
    int block=sqrt(n);
    tot=(n+block-1)/block;
    for(int i=1;i<=tot;i++){//分块
        L[i]=(i-1)*block+1,R[i]=min(i*block,n);
        for(int j=L[i];j<=R[i];j++)be[j]=i;
        cal(i);
    }
    while(q--){
        char op;
        int l,r,c;
        cin>>op>>l>>r>>c;
        if(op=='M'){
            if(be[l]==be[r]){
                for(int i=l;i<=r;i++)a[i]+=c;
                cal(be[l]);
                continue;
            }
            for(int i=l;i<=R[be[l]];i++)a[i]+=c;
            for(int i=L[be[r]];i<=r;i++)a[i]+=c;
            cal(be[l]);
            cal(be[r]);
            for(int i=be[l]+1;i<=be[r]-1;i++)tag[i]+=c;
            continue;
        }
        int ans=0;
        if(be[l]==be[r]){
            for(int i=l;i<=r;i++)ans+=(a[i]+tag[be[i]]>=c);
            cout<<ans<<"\n";
            continue;
        }
        for(int i=l;i<=R[be[l]];i++)ans+=(a[i]+tag[be[i]]>=c);
        for(int i=L[be[r]];i<=r;i++)ans+=(a[i]+tag[be[i]]>=c);
        for(int i=be[l]+1;i<=be[r]-1;i++){
            ans+=e+R[i]+1-lower_bound(e+L[i],e+R[i]+1,c-tag[i]);
        }
        cout<<ans<<"\n";
    }
}

分块 ​

分块