题解：P13977 数列分块入门 2

· · 题解

显然这个我们入手角度就是对于整个块怎么进行处理，我们显然可以发现。小于等于如果暴力就是 O(n)，但是如果我们以有序数组二分那就是 O(\log n)。思想就是对于块要维护有序。对于区间加，散列块我们需要重新建块进行 sort 排序。对于查询，我们可以对散列块暴力找，整块二分找。区间加对于大块来说是都加上一个数，不会改变相对大小的顺序所以只需要打 tag 就可以啦，时间复杂度 O(n\sqrt{n}\log n )。

5 万年前的代码：

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int MN=5e5+15,MQ=700;
int n;
vector<int> bl[MQ];
int l[MQ],r[MQ],pos[MN],tag[MQ],a[MN],len;
void init(){
    len=sqrt(n);
    for(int i=1;i<=len;i++){
        l[i]=r[i-1]+1;
        r[i]=i*len;
    }
    if(r[len]<n){
        r[++len]=n;
        l[len]=r[len-1]+1;
    }
    for(int i=1;i<=len;i++){
        for(int j=l[i];j<=r[i];j++){
            pos[j]=i;
            bl[i].push_back(a[j]);
        }
        sort(bl[i].begin(),bl[i].end());//处理完后要排序
    }
}
void bladd(int fl,int fr,int k){//暴力加
    int ql=pos[fl];
    for(int i=fl;i<=fr;i++){
        a[i]+=k;
    }
    bl[ql].clear();
    for(int i=l[ql];i<=r[ql];i++){
        bl[ql].push_back(a[i]);
    }
    sort(bl[ql].begin(),bl[ql].end());
}
void add(int fl,int fr,int k){//区间加操作
    int ql=pos[fl],qr=pos[fr];
    if(ql==qr){
        bladd(fl,fr,k);
        return;
    }
    bladd(fl,r[ql],k);
    bladd(l[qr],fr,k);
    for(int i=ql+1;i<qr;i++){
        tag[i]+=k;
    }
}
int query(int fl,int fr,int k){
    int ql=pos[fl],qr=pos[fr],ret=0;
    if(ql==qr){
        for(int i=fl;i<=fr;i++){
            if(a[i]+tag[ql]<k){
                ret++;
            }
        }
        return ret;
    }
    //两边暴力大块二分
    //分块九讲对于暴力写的是推到一个数组排序后二分，但是直接暴力也是可以的吧
    for(int i=fl;i<=r[ql];i++){
        if(a[i]+tag[ql]<k){
            ret++;
        }
    }
    for(int i=l[qr];i<=fr;i++){
        if(a[i]+tag[qr]<k){
            ret++;
        }
    }
    for(int i=ql+1;i<qr;i++){
        ret+=lower_bound(bl[i].begin(),bl[i].end(),k-tag[i])-bl[i].begin();
    }
    return ret;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init();
    while (n--)
    {
        int op,l,r,k;
        cin>>op>>l>>r>>k;
        if(op==0){
            add(l,r,k);
        }else cout<<query(l,r,k*k)<<endl;
    }

    return 0;
}