提交时间:2022-02-16 13:15:33
运行 ID: 45230
//array3 #include <bits/stdc++.h> using namespace std; #define inf 0x7f7f7f7f #define ll long long #define N 1000009 using namespace std; ll v[N],tag[N]; vector<ll> a[2600]; int blo[N]; int n,blo_len; ll read() { char ch=getchar(); ll f=1,ret=0; while(ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=ret*10+ch-'0'; ch=getchar(); } return ret; } void reinit(int x) { a[x].clear(); for (int i=(x-1)*blo_len+1; i<=min(n,x*blo_len); i++) a[x].push_back(v[i]); sort(a[x].begin(),a[x].end()); } void change(int l,int r,int d) { for (int i=l; i<=min(blo[l]*blo_len,r); i++) v[i]+=d; reinit(blo[l]); if (blo[l]!=blo[r]) { for (int i=(blo[r]-1)*blo_len+1; i<=r; i++) v[i]+=d; reinit(blo[r]); } for (int i=blo[l]+1; i<=blo[r]-1; i++) tag[i]+=d; } ll query(int l,int r,int d) { ll ret=-inf,cur; for (int i=l; i<=min(blo[l]*blo_len,r); i++) { cur=v[i]+tag[blo[l]]; if (cur<d&&cur>ret) ret=cur; } if (blo[l]!=blo[r]) for (int i=(blo[r]-1)*blo_len+1; i<=r; i++) { cur=v[i]+tag[blo[r]]; if (cur<d&&cur>ret) ret=cur; } for (int i=blo[l]+1; i<=blo[r]-1; i++) { int x=d-tag[i],id=lower_bound(a[i].begin(),a[i].end(),x)-a[i].begin()-1; if (a[i][id]<x) ret=max(ret,a[i][id]+tag[i]); } return ret==-inf?-1:ret; } int main() { n=read(); blo_len=sqrt(n); for (int i=1; i<=n; i++) v[i]=read(); for (int i=1; i<=n; i++) blo[i]=(i-1)/blo_len+1,a[blo[i]].push_back(v[i]); for (int i=1; i<=blo[n]; i++) sort(a[i].begin(),a[i].end()); for (int i=1; i<=n; i++) { int opt=read(),l=read(),r=read(); ll d=read(); if (!opt) change(l,r,d); else printf("%lld\n",query(l,r,d)); } return 0; }