题解：P13978 数列分块入门 3

Defy_HeavenS · 2025-09-07 13:14:25 · 题解

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

#6279. 数列分块入门 3 - 题目 - LibreOJ

题面

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的前驱（比其小的最大元素）。

技巧

仍然是块内排序，同上一道题。

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

这题出的不好，和上一题几乎一样，但作者是想让我们在块里维护 set。所以这题另外的技巧是可以在块里维护数据结构。

代码

const LL N=1e5+5,M=320,Inf=1e16+7;
LL n,T,tot,be[M],en[M],bel[N],tag[M];
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=-Inf;
        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) tmax(res,a[i].fi+tag[bel[i]]);
        }
        return res;
    }
    LL res=-Inf;
    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) tmax(res,a[i].fi+tag[bel[i]]);
    }
    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) tmax(res,a[i].fi+tag[bel[i]]);
    }
    for(LL i=bel[l]+1;i<=bel[r]-1;i++){
        LL L=be[i],R=en[i],mid,ans=-Inf;
        while(L<=R){
            mid=L+R>>1;
            if(a[mid].fi+tag[bel[mid]]<val){
                ans=a[mid].fi+tag[bel[mid]],L=mid+1;
            }else{
                R=mid-1;
            }
        }
        tmax(res,ans);
    }
    return res;
}

signed main(){
    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){
            LL res=query(l,r,c);
            cout<<(res==-Inf?-1:res)<<"\n";
        }else{
            update(l,r,c);
        }
    }
    return 0;
}