提交记录

#include <bits/stdc++.h>
using namespace std;
#define int long long  
const int N=1e5+5;
inline int read() {
	int s=0,t=1;
	char ch=getchar();
	while (ch<'0'|ch>'9') {
		if (ch=='-') t=-1;
		ch=getchar();
	}
	while (ch>='0'&ch<='9') {
		s=(s<<1)+(s<<3)+ch-'0';
		ch=getchar();
	}
	return s*t;
}
int n,m,a[N],cl[N],L[N],R[N],pos[N],mk[N],c[N];
int merge(int l,int r,int x) {
	while (l<r) {
		int mid=l+r+1>>1;
		if (cl[mid]+mk[pos[mid]]>x) r=mid-1;
		else l=mid;
	}
	return r;
}
signed main() {
	n=read(),m=read();
	for (int i=1;i<=n;i++) {
		a[i]=read();
		cl[i]=a[i];
	}
	int len=sqrt(n*1.0);
	for (int i=1;i<=len;i++) {
		L[i]=(i-1)*len+1;
		R[i]=i*len;
	}
	if (R[len]!=n) {
		len++;
		L[len]=R[len-1]+1;
		R[len]=n;
	}
	for (int i=1;i<=len;i++) {
		for (int j=L[i];j<=R[i];j++) {
			pos[j]=i;
		}
		sort(cl+L[i],cl+R[i]+1); 
	}
	int opt,l,r,x;
	while (m--) {
		opt=read(),l=read(),r=read(),x=read();
		if (opt==2) {
			if (pos[l]==pos[r]) {
				for (int i=l;i<=r;i++) {
					a[i]+=x;
				}
				for (int i=L[pos[l]];i<=R[pos[l]];i++) {
					cl[i]=a[i];
				}
				sort(cl+L[pos[l]],cl+R[pos[l]]+1);
			}
			else {
				for (int i=l;i<=R[pos[l]];i++) {
					a[i]+=x;
				}
				for (int i=L[pos[l]];i<=R[pos[l]];i++) {
					cl[i]=a[i];
				}
				sort(cl+L[pos[l]],cl+R[pos[l]]+1);
				for (int i=L[pos[r]];i<=r;i++) {
					a[i]+=x;
				}
				for (int i=L[pos[r]];i<=R[pos[r]];i++) {
					cl[i]=a[i];
				}
				sort(cl+L[pos[r]],cl+R[pos[r]]+1);
				for (int i=pos[l]+1;i<=pos[r]-1;i++) {
					mk[i]+=x;
				}
			}
		}
		else {
			int rk;
			if (r-l+1<x||x<=0) {
				printf ("-1\n");
				continue;
			}
//			printf ("%lld %lld\n",l,r);
			if (pos[l]==pos[r]) {
				for (int i=l;i<=r;i++) {
					c[i]=a[i]+mk[pos[l]];
				}
				sort(c+l,c+r+1);
				printf ("%lld\n",c[x]);
			}
			else {
				int ll=2e9,rr=-2e9;
				for (int i=l;i<=R[pos[l]];i++) {
					ll=min(ll,a[i]+mk[pos[l]]);
					rr=max(rr,a[i]+mk[pos[l]]);
				}
				for (int i=L[pos[r]];i<=r;i++) {
					ll=min(ll,a[i]+mk[pos[r]]);
					rr=max(rr,a[i]+mk[pos[r]]);
				}
				for (int i=pos[l]+1;i<=pos[r]-1;i++) {
					ll=min(ll,cl[L[i]]+mk[i]);
					rr=max(rr,cl[R[i]]+mk[i]);
				}
				if (x==1) {
					printf ("%lld\n",ll);
					continue;
				} 
				if (x==r-l+1) {
					printf ("%lld\n",rr);
					continue;
				}
				int ans; 
				while (ll<rr) {
					rk=1;
					int mid=ll+rr>>1;
					for (int i=l;i<=R[pos[l]];i++) {
						if (a[i]+mk[pos[l]]<=mid) rk++;
					}
					for (int i=L[pos[r]];i<=r;i++) {
						if (a[i]+mk[pos[r]]<=mid) rk++;
					}
					for (int i=pos[l]+1;i<=pos[r]-1;i++) {
						int w1=merge(L[i],R[i],mid);
						rk+=w1-L[i]+1;
//						printf ("%lld %lld %lld %lld\n",w1,cl[w1],mk[i],mid);
					}
//					printf ("%lld %lld %lld\n",mid,rk,rk2);
					if (rk>=x) {
						ans=mid;
						rr=mid-1;
					}
					else {
						ll=mid+1;
					}
				}
				printf ("%lld\n",ans);
			}
		}
	}
	return 0;
}
/*
10 3
4 2 2 4 5 3 8 3 5 7
1 3 10 2
2 3 10 2
1 3 10 2
*/