题解：P13977 数列分块入门 2

· · 题解

可以参考我的分块合集 分块。

#6278. 数列分块入门 2 - 题目 - LibreOJ

题面

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的元素个数。

技巧

由于小于某个值 x 的元素个数具有单调性，所以分完块后在块内排序。散块查询修改都直接暴力，但是修改后要重新排序；整块查询二分、修改用 tag。

时间复杂度。设块长为 T，预处理 \mathcal{O}(n\log n)，修改 \mathcal{O}(T\log T+\frac{n}{T})，查询 \mathcal{O}(T+\frac{n}{T}\log T)。最优块长是 \sqrt{n}。

代码

#include<bits/stdc++.h>
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define tmax(a,b) (a)=max((a),(b))
#define tmin(a,b) (a)=min((a),(b))

using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;

const LL N=2e5+5,M=555;
LL n,T,tot,be[M],en[M],bel[N],tag[N];
PII a[N];

void init(){
    T=tot=sqrt(n);
    for(LL i=1;i<=tot;i++){
        be[i]=en[i-1]+1,en[i]=i*T;
    }
    en[tot]=n;
    for(LL i=1;i<=tot;i++){
        for(LL j=be[i];j<=en[i];j++){
            bel[j]=i;
        }
        sort(a+be[i],a+en[i]+1);
    }
}
void update(LL l,LL r,LL val){
    if(bel[l]==bel[r]){
        for(LL i=be[bel[l]];i<=en[bel[r]];i++){
            if(l<=a[i].se&&a[i].se<=r) a[i].fi+=val;
        }
        sort(a+be[bel[l]],a+en[bel[r]]+1);
        return;
    }
    for(LL i=be[bel[l]];i<=en[bel[l]];i++){
        if(l<=a[i].se&&a[i].se<=r) a[i].fi+=val;
    }
    sort(a+be[bel[l]],a+en[bel[l]]+1);
    for(LL i=be[bel[r]];i<=en[bel[r]];i++){
        if(l<=a[i].se&&a[i].se<=r) a[i].fi+=val;
    }
    sort(a+be[bel[r]],a+en[bel[r]]+1);
    for(LL i=bel[l]+1;i<=bel[r]-1;i++){
        tag[i]+=val;
    }
}
LL query(LL l,LL r,LL val){
    if(bel[l]==bel[r]){
        LL res=0;
        for(LL i=be[bel[l]];i<=en[bel[r]];i++){
            if(l<=a[i].se&&a[i].se<=r&&a[i].fi+tag[bel[i]]<val) res++;
        }
        return res;
    }
    LL res=0;
    for(LL i=be[bel[l]];i<=en[bel[l]];i++){
        if(l<=a[i].se&&a[i].se<=r&&a[i].fi+tag[bel[i]]<val) res++;
    }
    for(LL i=be[bel[r]];i<=en[bel[r]];i++){
        if(l<=a[i].se&&a[i].se<=r&&a[i].fi+tag[bel[i]]<val) res++;
    }
    for(LL i=bel[l]+1;i<=bel[r]-1;i++){
        LL L=be[i],R=en[i],mid,ans=be[i]-1;
        while(L<=R){
            mid=L+R>>1;
            if(a[mid].fi+tag[bel[mid]]<val){
                ans=mid,L=mid+1;
            }else{
                R=mid-1;
            }
        }
        res+=ans-be[i]+1;
    }
    return res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(LL i=1;i<=n;i++){
        cin>>a[i].fi;
        a[i].se=i;
    }
    init();
    for(LL i=1,op,l,r,c;i<=n;i++){
        cin>>op>>l>>r>>c;
        if(op){
            c*=c;
            cout<<query(l,r,c)<<"\n";
        }else{
            update(l,r,c);
        }
    }
    return 0;
}
/*

*/