萌新分块球调，悬赏1关注

#include<bits/stdc++.h>
#define int long long

using namespace std;

static int read(){
	int s=0,w=1;char c=getchar();
	while(c<'0' || c>'9'){ if(c=='-') w=-1;c=getchar();}
	while(c>='0' && c<='9'){ s=(s<<3)+(s<<1)+c-48;c=getchar();}
	return s*w;
}

const int N=2e5+5;

int n,m,a[N],b[N];
int len,bl[N],L[N],R[N],tag[N];

static void reset(int x){
	for(int i=L[x];i<=R[x];i++) b[i]=a[i];
	sort(b+L[x],b+R[x]+1);
}

static void update(int l,int r,int d){
	for(int i=l;i<=min(r,R[bl[l]]);i++)
		a[i]+=d;
	reset(bl[l]);
	if(bl[l]!=bl[r]){
		for(int i=L[bl[r]];i<=r;i++)
			a[i]+=d;
		reset(bl[r]);
	}
	for(int i=bl[l]+1;i<=bl[r]-1;i++)
		tag[i]+=d;
}

static int calc(int l,int r,int x){
	int cnt=0;
	for(int i=l;i<=min(r,R[bl[l]]);i++)
		if(a[i]+tag[i]<=x) cnt++;
	if(bl[l]!=bl[r])
		for(int i=L[bl[r]];i<=r;i++)
			if(a[i]+tag[i]<=x) cnt++;
	for(int i=bl[l]+1;i<=bl[r]-1;i++){
		int ll=L[i],rr=R[i],mid;
		if(b[L[i]]+tag[i]>x) continue;
		if(b[R[i]]+tag[i]<=x){
			cnt+=R[i]-L[i]+1;
			continue;
		}
		while(ll<rr){
			mid=(ll+rr)/2+1;
			if(b[mid]+tag[i]<=x) ll=mid;
			else rr=mid-1;
		}
		if(b[ll]+tag[i]<=x) cnt+=ll-L[i]+1;
	}
	return cnt;
}

static int _getmin(int l,int r){
	int MIN=3000000005;
	for(int i=l;i<=min(r,R[bl[l]]);i++)
		MIN=min(MIN,a[i]+tag[bl[i]]);
	if(bl[l]!=bl[r])
		for(int i=L[bl[r]];i<=r;i++)
			MIN=min(MIN,a[i]+tag[bl[i]]);
	for(int i=bl[l]+1;i<=bl[r]-1;i++)
		MIN=min(MIN,b[L[i]]+tag[i]);
	return MIN;
}

static int _getmax(int l,int r){
	int MAX=-3000000005;
	for(int i=l;i<=min(r,R[bl[l]]);i++)
		MAX=max(MAX,a[i]+tag[bl[i]]);
	if(bl[l]!=bl[r])
		for(int i=L[bl[r]];i<=r;i++)
			MAX=max(MAX,a[i]+tag[bl[i]]);
	for(int i=bl[l]+1;i<=bl[r]-1;i++)
		MAX=max(MAX,b[R[i]]+tag[i]);
	return MAX;
}

static int query(int ll,int rr,int k){
	if(k<1 || k>rr-ll+1) return -1;
	int l=_getmin(ll,rr),r=_getmax(ll,rr);
	int ans=-1;
	while(l<=r){
		int mid=(l+r)/2;
		if(calc(ll,rr,mid)<k) l=mid+1;
		else{
			ans=mid;
			r=mid-1;
		}
	}
	return ans;
}

signed main(){
	n=read(),m=read();len=150;
	for(int i=1;i<=n;i++){
		a[i]=b[i]=read();
		bl[i]=(i-1)/len+1;
	}
	for(int i=1;i<=bl[n];i++)
		L[i]=(i-1)*len+1,R[i]=min(n,i*len);
	for(int i=1;i<=bl[n];i++)
		sort(b+L[i],b+R[i]+1);
	
	while(m--){
		int opt=read(),l=read(),r=read(),k=read();
		if(l>r) swap(l,r);
		if(opt==1) printf("%lld\n",query(l,r,k));
		else update(l,r,k);
	}
	
	return 0;
}