题解：P13977 数列分块入门 2

_zfz_ · 2025-09-06 22:53:41 · 题解

分块太好用了

本题是一道分块的模板题。分块，就是通过将序列分成固定长度的块（通常为 \sqrt{n}），从而降低区间操作（查询）的时间复杂度。

区间加的操作很简单，可以开一个数组 de 维护每一个块的整体的加的值。操作时，两端不纳入块范围的直接暴力加，中间的完整的块加 d_i 即可。

可询问就有点麻烦了，如果直接算，时间复杂度为 O(n)。那么，就有一种优化的方法：开一个数组，存每个块内排序后的情况，之后就可以直接二分，然后暴力统计两端，复杂度为 O(\sqrt{n} \log{n})。然后，在每次区间加的操作的操作后，对暴力加的块重新排序，复杂度为 O(\sqrt{n} \log{n})，可以通过此题。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
const int B=500;
int de[B],l[B],r[B],bel[N],sd[N],a[N],n,b;
void init(){
    b=sqrt(n);
    for(int i=1;i<=b;i++){
        l[i]=n/b*(i-1)+1;
        r[i]=n/b*i;
    }
    r[b]=n;
    for(int i=1;i<=b;i++)
        for(int j=l[i];j<=r[i];j++) bel[j]=i;
}
void Sort(int k){
    for(int i=l[k];i<=r[k];i++) sd[i]=a[i];
    sort(sd+l[k],sd+r[k]+1);
}
void add(int x,int y,int c){
    int ks=bel[x];
    int kd=bel[y];
    if(ks==kd){
        for(int i=x;i<=y;i++) a[i]+=c;
        Sort(ks);
        return;
    }
    for(int i=x;i<=r[ks];i++) a[i]+=c;
    for(int i=l[kd];i<=y;i++) a[i]+=c;
    for(int i=ks+1;i<kd;i++) de[i]+=c;
    Sort(ks);
    Sort(kd);
}
int query(int x,int y,int c){
    int ans=0,ks=bel[x],kd=bel[y];
    if(ks==kd){
        for(int i=x;i<=y;i++)
            if(a[i]+de[ks]<c) ans++;
        return ans;
    }
    for(int i=x;i<=r[ks];i++)
        if(a[i]+de[ks]<c) ans++;
    for(int i=l[kd];i<=y;i++)
        if(a[i]+de[kd]<c) ans++;
    for(int i=ks+1;i<kd;i++)
        ans+=(lower_bound(sd+l[i],sd+r[i]+1,c-de[i])-sd-l[i]);
    return ans;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    init();
    for(int i=1;i<=b;i++) Sort(i);
    for(int i=1;i<=n;i++){
        int m,x,y,c;
        cin>>m>>x>>y>>c;
        if(m==0)
            add(x,y,c);
        else
            cout<<query(x,y,c*c)<<endl;
    }
    return 0;
}