题解：P13977 数列分块入门 2

zhoujiefu · 2025-09-06 17:25:38 · 题解

做法

考虑分块。维护两个数组。一个是原数组，一个是块内排序后的数组。散块直接加，然后暴力重构。整块维护一个 tag，直接加。查询的时候，散块暴力查询，整块在排好序的数组上二分第一个小于 x 的位置计算答案。

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define sz(i) r[i]-l[i]+1
using namespace std;
const int N=2e5+5,B=500;
int n,q,tot;
int a[N],b[N],l[B],r[B],bel[N],tag[B];
inline void reset(int x){
    rep(i,l[x],r[x]) b[i]=a[i];
    sort(b+l[x],b+r[x]+1);
}
inline void update(int L,int R,int w){
    if(bel[L]==bel[R]){
        rep(i,L,R) a[i]+=w;
        reset(bel[L]);
        return;
    }
    rep(i,L,r[bel[L]]) a[i]+=w;
    rep(i,l[bel[R]],R) a[i]+=w;
    reset(bel[L]),reset(bel[R]);
    rep(i,bel[L]+1,bel[R]-1) tag[i]+=w;
}
inline int query(int L,int R,int w){
    int ans=0;
    if(bel[L]==bel[R]){
        rep(i,L,R) if(a[i]+tag[bel[i]]<w) ans++;
        return ans;
    }
    rep(i,L,r[bel[L]]) if(a[i]+tag[bel[i]]<w) ans++;
    rep(i,l[bel[R]],R) if(a[i]+tag[bel[i]]<w) ans++;
    rep(i,bel[L]+1,bel[R]-1) ans+=lower_bound(b+l[i],b+r[i]+1,w-tag[i])-b-l[i];
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    rep(i,1,n) cin>>a[i],b[i]=a[i];
    rep(i,1,n) bel[i]=i/B;
    rep(i,1,n) if(!l[bel[i]]) l[bel[i]]=i;
    per(i,n,1) if(!r[bel[i]]) r[bel[i]]=i;
    tot=bel[n];
    rep(i,1,tot) sort(b+l[i],b+r[i]+1);
    rep(i,1,n){
        int op,l,r,w;
        cin>>op>>l>>r>>w;
        if(op==1){
            cout<<query(l,r,w*w)<<'\n';
        }else{
            update(l,r,w);
        }
    }
    return 0;
}