AC on 8 10 20 22求条

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
long long a[200005],sta[200005],cnt,le[200005],ri[200005],pos[200005],tag[200005];
void build(int n)
{
    int len=sqrt(n)+1;
    while(true)
    {
        cnt++;
        le[cnt]=(cnt-1)*len+1;
        ri[cnt]=cnt*len;
        if(ri[cnt]>=n)
        {
            ri[cnt]=n;
            break;
        }
    }
    for(int j=1;j<=cnt;j++)
    {
        sort(sta+le[j],sta+ri[j]+1);
        for(int i=le[j];i<=ri[j];i++)
        {
            pos[i]=j;
        }
    }
    return ;
}
void update(int l,int r,int c)
{
    if(pos[l]==pos[r])
    {
        for(int i=l;i<=r;i++) a[i]+=c;
        for(int i=le[pos[l]];i<=ri[pos[l]];i++) sta[i]=a[i];
        sort(sta+le[pos[l]],sta+ri[pos[l]]+1);
        return ;
    }
    for(int i=l;i<=ri[pos[l]];i++) a[i]+=c;
    for(int i=le[pos[l]];i<=ri[pos[l]];i++) sta[i]=a[i];
    sort(sta+le[pos[l]],sta+ri[pos[l]]+1);
    for(int i=le[pos[r]];i<=r;i++) a[i]+=c;
    for(int i=le[pos[r]];i<=ri[pos[r]];i++) sta[i]=a[i];
    sort(sta+le[pos[r]],sta+ri[pos[r]]+1);
    for(int i=pos[l]+1;i<pos[r];i++) tag[i]+=c;
    return ;
}
int query(int l,int r,int c)
{
    long long maxn=-1e18;
    if(pos[l]==pos[r])
    {
        for(int i=l;i<=r;i++)
        {
            if(a[i]+tag[pos[i]]<c) maxn=max(maxn,a[i]+tag[pos[i]]);
        }
        return maxn;
    }
    for(int i=l;i<=ri[pos[l]];i++)
    {
        if(a[i]+tag[pos[i]]<c) maxn=max(maxn,a[i]+tag[pos[i]]);
    }
    for(int i=le[pos[r]];i<=r;i++)
    {
        if(a[i]+tag[pos[i]]<c) maxn=max(maxn,a[i]+tag[pos[i]]);
    }
    for(int i=pos[l]+1;i<pos[r];i++)
    {
        int lft=le[i],rht=ri[i]+1;
        while(lft<rht)
        {
            int mid=(lft+rht)/2;
            if(sta[mid]<c-tag[i]) lft=mid+1;
            else rht=mid;
        }
        if(lft>le[i])
        {
            maxn=max(maxn,sta[lft-1]+tag[i]);
        }
    }
    return maxn;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) sta[i]=a[i];
    build(n);
    for(int i=1;i<=n;i++)
    {
        int op,l,r,c;
        cin>>op>>l>>r>>c;
        if(op==0) update(l,r,c);
        else
        {
            long long ma=query(l,r,c);
            ma==-1e18 ? cout<<-1<<endl:cout<<ma<<endl;
        }
    }
    return 0;
}