题解：P13978 数列分块入门 3

· · 题解

当年还不会用 lower_bound 也不会手写二分的我被这题硬控一下午，我咋这么菜。

分析

区间加显然无需多言，非常好做，不做介绍。

考虑区间前驱怎么统计块与块间的贡献。这个由前驱的定义，就很好想：假设 f(l,r) 表示 v 在 [l,r] 中的前驱，x 是满足 l\le x\le r 的任意整数，那么总有 f(l,r)=\max(f(l,x),f(x+1,r))。

接下来考虑怎样在每个块内找某一个数的前驱。我们采取最简单粗暴的方式——将第 i 块中的所有数都拷贝到一个单独的数组中；然后将这个数组排序，并在这个数组中做二分查找。

散块暴力好搞，于是这道题就做完了。

代码

#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;

const int N=1e7+5;
const int M=1e4+5;

int n;
ll a[N];

namespace FK{

    int k/*块长*/,tot/*块数*/;
    ll la[M]/*la[i] -> 第 i 块上的懒标记*/;
    int L[M]/*L[i] -> 第 i 块的左端点*/,R[M]/*R[i] -> 第 i 块的右端点*/,loc[N]/*loc[i] -> 第 i 个数在第几块*/;
    ll b[M][M];//b[i] -> 第 i 块上排序后的数组

    inline void init(){
        k=sqrt(n);
        tot=(n+k-1)/k;
        for(int i=1;i<=tot;++i){
            L[i]=(i-1)*k+1;
            if(i==tot)R[i]=n;
            else R[i]=L[i]+k-1;
            int idx=0;
            for(int j=L[i];j<=R[i];++j){
                loc[j]=i;
                b[i][++idx]=a[j];
            }
            sort(b[i]+1,b[i]+R[i]-L[i]+1+1);
        }
        return ;
    }

    inline void pushdown(int i){
        if(la[i]==0)return ;
        int idx=0;
        for(int j=L[i];j<=R[i];++j)a[j]+=la[i];
        for(int j=1;j<=R[i]-L[i]+1;++j)b[i][j]+=la[i];
        return la[i]=0,void();
    }

    inline void upd(int l,int r,ll x){
        if(loc[l]==loc[r]){
            pushdown(loc[l]);
            for(int i=l;i<=r;++i)a[i]+=x;
            for(int i=1;i<=R[loc[l]]-L[loc[l]]+1;++i)b[loc[l]][i]=a[L[loc[l]]+i-1];
            sort(b[loc[l]]+1,b[loc[l]]+(R[loc[l]]-L[loc[l]]+1)+1);
        }else{
            pushdown(loc[l]),pushdown(loc[r]);
            for(int i=l;i<=R[loc[l]];++i)a[i]+=x;
            for(int i=1;i<=R[loc[l]]-L[loc[l]]+1;++i)b[loc[l]][i]=a[L[loc[l]]+i-1];
            sort(b[loc[l]]+1,b[loc[l]]+(R[loc[l]]-L[loc[l]]+1)+1);
            for(int i=L[loc[r]];i<=r;++i)a[i]+=x;
            for(int i=1;i<=R[loc[r]]-L[loc[r]]+1;++i)b[loc[r]][i]=a[L[loc[r]]+i-1];
            sort(b[loc[r]]+1,b[loc[r]]+(R[loc[r]]-L[loc[r]]+1)+1);
            for(int i=loc[l]+1;i<=loc[r]-1;++i)la[i]+=x;
        }
        return ;
    }

    inline ll qry(int l,int r,ll x){
        ll s=-1e18;
        if(loc[l]==loc[r]){
            pushdown(loc[l]);
            for(int i=l;i<=r;++i)if(a[i]<x)s=max(s,a[i]);
        }else{
            pushdown(loc[l]),pushdown(loc[r]);
            for(int i=l;i<=R[loc[l]];++i)if(a[i]<x)s=max(s,a[i]);
            for(int i=L[loc[r]];i<=r;++i)if(a[i]<x)s=max(s,a[i]);
            for(int i=loc[l]+1;i<=loc[r]-1;++i){
                int p=lower_bound(b[i]+1,b[i]+R[i]-L[i]+1+1,x-la[i])-b[i]-1;//二分，此时从 b[i][p] 往后的所有数都严格大于 x，那么 b[i][p] 就是第 i 块上的答案。
                if(p>0)s=max(s,b[i][p]+la[i]);//实际计算时还要考虑懒标记的影响。
            }
        }
        return s!=-1e18?s:-1;
    }

}using namespace FK;

inline void work(){
    int op,l,r;ll c;
    cin>>op>>l>>r>>c;
    if(1==2)puts("wow");
    else if(op==0)upd(l,r,c);
    else if(op==1)cout<<qry(l,r,c)<<"\n";
    return ;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    init();
    while(n--)work();
    return 0;
}

#undef ll