P13978 数列分块入门 3 题解

· · 题解

题面解释：

分块维护区间加，区间查询前驱。

思路分析：

思路与教主的魔法完全相同。

散块直接暴力。修改时直接加，查询时也是直接枚举。

对于整块暴力排序，二分查询。每次被当做散块修改后都进行排序，保证其单调性。查询的时候由于保证单调性直接二分查找即可。

AC Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,p,q,a[N],b[N],c[N];
void resort(int id){
    int l=id*q,r=min(l+q-1,n-1);
    for(int i=l;i<=r;i++)c[i]=a[i];
    sort(c+l,c+r+1);
}
int query(int id,int v){
    int l=id*q,r=min(l+q-1,n-1);
    v-=b[id];
    if(c[l]>=v)return LLONG_MIN;
    int L=l,R=r,res;
    while(L<=R){
        int mid=L+R>>1;
        if(c[mid]<v)L=mid+1,res=mid;
        else R=mid-1;
    }
    return c[res]+b[id];
}
signed main(){
    scanf("%lld",&n);
    q=(int)sqrt(n/log(n));
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]),c[i]=a[i];
    for(int l=0,r;l<n;l+=q){
        r=min(l+q-1,n-1);
        sort(c+l,c+r+1);
    }
    for(int T=1;T<=n;T++){
        int op,l,r,m;
        scanf("%lld%lld%lld%lld",&op,&l,&r,&m);
        l--;r--;
        if(op==0){
            int _l=l,_r=r;
            for(;l%q&&l<=r;l++)a[l]+=m;
            for(;l+q-1<=r;l+=q)b[l/q]+=m;
            for(;l<=r;l++)a[l]+=m;
            resort(_l/q);
            if(_l/q!=_r/q)resort(_r/q);
        }
        else{
            int ans=LLONG_MIN;
            for(;l%q&&l<=r;l++)if(a[l]+b[l/q]<m)ans=max(ans,a[l]+b[l/q]);
            for(;l+q-1<=r;l+=q)ans=max(ans,query(l/q,m));
            for(;l<=r;l++)if(a[l]+b[l/q]<m)ans=max(ans,a[l]+b[l/q]);
            if(ans==LLONG_MIN)ans=-1;
            printf("%lld\n",ans);
        }
    }
    return 0;
}