AC#8#10#20#22求调

#include<iostream>
#include<cmath>
#include<algorithm>
#include<climits>
#define ll long long
#define MAXN 200005
using namespace std;
ll a[MAXN],b[MAXN];
int belong[MAXN];
int L[MAXN],R[MAXN];
ll add[MAXN];
void upd(int l,int r,ll c){
    for(int i=l;i<=r;i++) a[i]+=c;
    for(int i=L[belong[l]];i<=R[belong[l]];i++) b[i]=a[i];
    sort(b+L[belong[l]],b+R[belong[l]]+1);
}
ll query(int l,int r,ll c){
    ll ans=LLONG_MIN;
    for(int i=l;i<=r;i++){
        if(a[i]+add[belong[i]]<c) ans=max(ans,a[i]+add[belong[i]]);
    }
    return ans;
}
int main(){
    int n,q;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    q=n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        b[i]=a[i];
    }
    int len=sqrt(n),cnt=(n+len-1)/len;
    for(int i=1;i<=cnt;i++){
        L[i]=R[i-1]+1;
        R[i]=min(L[i]+len-1,n);
        for(int j=L[i];j<=R[i];j++){
            belong[j]=i;
        }
        sort(b+L[i],b+R[i]+1);
    }
    while(q--){
        bool op;
        int l,r;
        ll c;
        cin >> op >> l >> r >> c;
        if(!op){
            if(belong[l]==belong[r]){
                upd(l,r,c);
            }
            else{
                upd(l,R[belong[l]],c);
                upd(L[belong[r]],r,c);
                for(int i=belong[l]+1;i<belong[r];i++){
                    add[i]+=c;
                }
            }
        }
        else{
            if(belong[l]==belong[r]){
                cout << query(l,r,c) << '\n';
            }
            else{
                ll ans=LLONG_MIN;
                ans=max(ans,query(l,R[belong[l]],c));
                ans=max(ans,query(L[belong[r]],r,c));
                for(int i=belong[l]+1;i<belong[r];i++){
                    int l_=L[i],r_=R[i];
                    while(l_<=r_){
                        int mid=(l_+r_)>>1;
                        if(b[mid]<c-add[i]) l_=mid+1;
                        else r_=mid-1;
                    }
                    if(r_>=L[i]) ans=max(ans,b[r_]+add[i]);
                }
                if(ans!=LLONG_MIN) cout << ans << '\n';
                else cout << -1 << '\n';
            }
        }
    }
    return 0;
}