rt.

由乃打扑克

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+10,M=1e5+10;
struct node{
	int id,k;
	bool operator<(const node &x)const{
		return k<x.k;
	}
}a[N],c[M],d[M],e[M];
struct kuai{
	int l,r,maxn,minn,tag;
	kuai(){
		maxn=-1e18,minn=1e18;
	}
}b[N]; 
int n,m,len;
int ce,cc,cd,f[M],cf,dy[N];
int k=1;
inline void init(){
	for(int i=1;i<=n;i+=len,k++){
		b[k].l=i,b[k].r=min(i+len-1,n);
		for(int j=b[k].l;j<=b[k].r;++j){
			b[k].maxn=max(b[k].maxn,a[j].k);
			b[k].minn=min(b[k].minn,a[j].k); 
		}
		sort(a+b[k].l,a+b[k].r+1);
	}
//	for(int i=1;i<=k;++i) cout<<b[i].l<<' '<<b[i].r<<endl;
}
inline void gb(){
	ce=0;
	int pc=1,pd=1;	
	while(pc<=cc&&pd<=cd){
		if(c[pc].k<=d[pd].k) e[++ce]=c[pc++];
		else e[++ce]=d[pd++];
	}
	while(pc<=cc) e[++ce]=c[pc++];
	while(pd<=cd) e[++ce]=d[pd++];
}

inline int qk(int x){
	if(x%len==0) return x/len;
	return x/len+1;
}

inline void change(int l,int r,int p){
	if(qk(l)==qk(r)){
		//左右两边在同一个块 
		cc=0,cd=0;
		for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i){ 
			if(l<=a[i].id&&a[i].id<=r) a[i].k+=p,c[++cc]={a[i].id,a[i].k};
			else d[++cd]={a[i].id,a[i].k};
		}
		
//		for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i) cout<<a[i].k<<' '<<a[i].id<<'\n';
//		cout<<'#'<<endl;
		
		gb();
		for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i) a[i]=e[i-b[qk(l)].l+1];
		
//		for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i) cout<<e[i-b[qk(l)].l+1].k<<' '<<e[i-b[qk(l)].l+1].id<<'\n';
//		cout<<'#'<<endl;

		b[qk(l)].maxn=a[b[qk(l)].r].k+b[qk(l)].tag,b[qk(l)].minn=a[b[qk(l)].l].k+b[qk(l)].tag;
		return;
	}
//	cout<<'C'<<L<<' '<<R<<endl;
	for(int i=qk(l)+1;i<=qk(r)-1;++i) b[i].maxn+=p,b[i].minn+=p,b[i].tag+=p;
	//左端点 l~L-1
	cc=0,cd=0;
	for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i){
		if(l<=a[i].id&&a[i].id<=r) c[++cc]={a[i].id,a[i].k+p};
		else d[++cd]={a[i].id,a[i].k};
	} 
	gb();
	for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i) a[i]=e[i-b[qk(l)].l+1];
	b[qk(l)].minn=a[b[qk(l)].l].k+b[qk(l)].tag,b[qk(l)].maxn=a[b[qk(l)].r].k+b[qk(l)].tag;
	//右端点 R+1~r
	cc=0,cd=0;
	for(int i=b[qk(r)].l;i<=b[qk(r)].r;++i){
		if(l<=a[i].id&&a[i].id<=r) c[++cc]={a[i].id,a[i].k+p};
		else d[++cd]={a[i].id,a[i].k};
	}
	gb();
	for(int i=b[qk(r)].l;i<=b[qk(r)].r;++i) a[i]=e[i-b[qk(r)].l+1];
	b[qk(r)].maxn=a[b[qk(r)].r].k+b[qk(r)].tag,b[qk(r)].minn=a[b[qk(r)].l].k+b[qk(r)].tag;
	
	//调试 
//	for(int i=1;i<=n;++i) cout<<a[i].id<<' '<<a[i].k<<" #";
//	cout<<endl;
//	for(int i=1;i<=k;++i) cout<<b[i].l<<' '<<b[i].r<<' '<<b[i].minn<<' '<<b[i].maxn<<' '<<b[i].tag<<endl;
//	cout<<'!'<<endl;
}
inline int qsum(int l,int r,int x){
	if(qk(l)==qk(r)){
		int sum=0;
		for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i){
			if(l<=a[i].id&&a[i].id<=r&&a[i].k+b[qk(l)].tag<=x) sum++; 
		}
		return sum;
	}
	int sum=0;
	int L=b[qk(l)+1].r;
	int R=b[qk(r)-1].r;
	for(int i=qk(l)+1;i<=qk(r)-1;++i){
		int k=upper_bound(a+b[i].l,a+b[i].r+1,node({100000,x-b[i].tag}))-a;
		sum+=k-b[i].l;
	}
//	cout<<l<<' '<<r<<' '<<x<<' '<<sum<<endl;
	//散块暴力找
	//左 
	for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i) 
		if(l<=a[i].id&&a[i].k+b[qk(l)].tag<=x) sum++;
	//右
	for(int i=b[qk(r)].l;i<=b[qk(r)].r;++i){
		if(a[i].id<=r&&a[i].k+b[qk(r)].tag<=x) sum++;
	} 
	return sum;                                                                                 
}
inline void query(int l,int r,int p){
	if(r-l+1<p){
		cout<<-1<<endl;
		return; 
	}
	if(qk(l)==qk(r)){ 
		if(p==1){
			int minn=1e18;
			for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i){
				if(a[i].id>=l&&a[i].id<=r) minn=min(a[i].k+b[qk(l)].tag,minn);
			}
			cout<<minn<<endl;
			return;
		}
		cf=0;
		for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i) if(l<=a[i].id&&a[i].id<=r) f[++cf]=a[i].k+b[qk(l)].tag;
		sort(f+1,f+cf+1);
//		cout<<cf<<endl;	
		int sum=1;
		if(cf>=p) cout<<f[p]<<endl;
		else cout<<-1<<endl;
		return;
	}
	int l_=1e18,r_=-1e18,ans=1e18;
//	cout<<L<<' '<<R<<endl;
	for(int i=qk(l)+1;i<=qk(r)-1;++i) l_=min(l_,b[i].minn),r_=max(r_,b[i].maxn);
//	cout<<l_<<' '<<r_<<endl;
	for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i){
		if(a[i].id>=l) l_=min(l_,a[i].k+b[qk(l)].tag),r_=max(r_,a[i].k+b[qk(l)].tag);
	}
//	cout<<l_<<' '<<r_<<endl;
	for(int i=b[qk(r)].l;i<=b[qk(r)].r;++i){
		if(a[i].id<=r) l_=min(l_,a[i].k+b[qk(r)].tag),r_=max(r_,a[i].k+b[qk(r)].tag);
	}
//	cout<<l_<<' '<<r_<<endl;
	while(l_<=r_){
		int mid=(l_+r_)>>1;
		if(qsum(l,r,mid)>=p) r_=mid-1,ans=mid;
		else l_=mid+1;
	}
	if(ans!=1e18) cout<<ans<<endl; 
	else cout<<-1<<endl;
}
signed main(){
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	len=700;
	for(int i=1;i<=n;++i) cin>>a[i].k,a[i].id=i;
	init();
//	for(int i=1;i<=n;++i) cout<<a[i].k<<' '<<a[i].id<<endl;
//	cout<<'#'<<endl;
//	cout<<m<<endl;
	for(int i=1;i<=m;++i){
		int op,l,r,k;
		cin>>op>>l>>r>>k; 
		if(op==1) query(l,r,k);
		else change(l,r,k);
//			cout<<'q'<<qsum(1,5,7)<<endl;
	}
	return 0;
}