LuoguP5356 [Ynoi2017] 由乃打扑克

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10,S=250,M=N/S+10;
int n,m,tot,g[M],mn[M],mx[N];
vector<int> b[M],s[M];
I void B(CI x){s[x]=b[x],sort(s[x].begin(),s[x].end()),mn[x]=*s[x].begin(),mx[x]=*s[x].rbegin();}
I bool check(CI bL,CI bR,CI l,CI r,CI mid,CI k){
    RI i,S=0;if(bL==bR){for(i=l;i<=r;i++) if(b[bL][i]+g[bL]<=mid) S++;return S>=k;}
    for(i=l;i<b[bL].size();i++) if(b[bL][i]+g[bL]<=mid) S++;for(i=0;i<=r;i++) if(b[bR][i]+g[bR]<=mid) S++;
    for(i=bL+1;i<=bR-1;i++) if(mx[i]+g[i]<=mid) S+=b[i].size();
    else if(mn[i]+g[i]<=mid) S+=(upper_bound(s[i].begin(),s[i].end(),mid-g[i])-s[i].begin());return S>=k; 
}
I int Gmn(RI l,RI r){
    RI i,bL=1,bR=1,S=2e9;W(l>=b[bL].size()) l-=b[bL++].size();W(r>=b[bR].size()) r-=b[bR++].size();
    if(bL==bR){for(i=l;i<=r;i++) S=min(S,b[bL][i]+g[bL]);return S;}
    for(i=l;i<b[bL].size();i++) S=min(S,b[bL][i]+g[bL]);for(i=0;i<=r;i++) S=min(S,b[bR][i]+g[bR]);
    for(i=bL+1;i<=bR-1;i++) S=min(S,*s[i].begin()+g[i]);return S;
}
I int Gmx(RI l,RI r){
    RI i,bL=1,bR=1,S=-2e9;W(l>=b[bL].size()) l-=b[bL++].size();W(r>=b[bR].size()) r-=b[bR++].size();
    if(bL==bR){for(i=l;i<=r;i++) S=max(S,b[bL][i]+g[bL]);return S;}
    for(i=l;i<b[bL].size();i++) S=max(S,b[bL][i]+g[bL]);for(i=0;i<=r;i++) S=max(S,b[bR][i]+g[bR]);
    for(i=bL+1;i<=bR-1;i++) S=max(S,*s[i].rbegin()+g[i]);return S;
}
I int Q(RI l,RI r,CI k){
    if(r-l+1<k) return -1;RI i,L=Gmn(l,r),R=Gmx(l,r),S=2e9+1,mid,bL=1,bR=1;W(l>=b[bL].size()) l-=b[bL++].size();W(r>=b[bR].size()) r-=b[bR++].size();
    W(L<=R) check(bL,bR,l,r,mid=(1LL*L+R>>1),k)?(S=mid,R=mid-1):L=mid+1;return S==2e9+1?-1:S;
}
I void U(RI l,RI r,CI k){
    RI i,bL=1,bR=1;W(l>=b[bL].size()) l-=b[bL++].size();W(r>=b[bR].size()) r-=b[bR++].size();
    if(bL==bR){for(i=l;i<=r;i++) b[bL][i]+=k;return B(bL);}
    for(i=l;i<b[bL].size();i++) b[bL][i]+=k;B(bL);for(i=0;i<=r;i++) b[bR][i]+=k;B(bR);
    for(i=bL+1;i<=bR-1;i++) g[i]+=k;
}
int main(){ 
    RI i,x,opt,l,r,k;for(read(n,m),i=0;i<n;i++) read(x),b[i/S+1].push_back(x);tot=(n-1)/S+1;
    for(i=1;i<=tot;i++) B(i);for(i=1;i<=m;i++) if(read(opt,l,r,k),opt==1) writeln(Q(l-1,r-1,k));
    else U(l-1,r-1,k);return 0;
}