蒟蒻，0分求调分块（qwq）

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,a[N],b[N],add[N];
int op,x,y,k;
int block,cnt,l[N],r[N],pos[N];
void build_block(){
	block=sqrt(n);
	cnt=n/block;
	if(n%block) cnt++;
	for(int i=1;i<=cnt;i++)
		l[i]=(i-1)*block+1,r[i]=i*block;
	r[cnt]=n;
	for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1;
	for(int i=1;i<=cnt;i++)
		sort(b+l[i],b+r[i]+1);
}
void modify(int L,int R,int v){
	int p=pos[L],q=pos[R];
	if(p==q){
		for(int i=L;i<=R;i++) a[i]+=v;
		for(int i=l[p];i<=r[p];i++) b[i]=a[i];
		sort(b+l[p],b+r[p]+1);
	}else{
		for(int i=p+1;i<=q-1;i++) add[i]+=v;
		for(int i=L;i<=r[p];i++) a[i]+=v;
		for(int i=l[p];i<=r[p];i++) b[i]=a[i];
		sort(b+l[p],b+r[p]+1);
		for(int i=l[q];i<=R;i++) a[i]+=v;
		for(int i=l[q];i<=r[q];i++) b[i]=a[i];
		sort(b+l[q],b+r[q]+1); 
	}
}
int query(int L,int R,int c){
	int p=pos[L],q=pos[R],ans=0;
	if(p==q){
		for(int i=L;i<=R;i++)
			if(a[i]+add[p]<c) ans++; 
	}else{
		for(int i=L;i<=r[p];i++)
			if(a[i]+add[p]<c) ans++;
		for(int i=l[q];i<=R;i++)
			if(a[i]+add[q]<c) ans++;
		for(int i=p+1;i<=q-1;i++){
			int ll=l[i],rr=r[i],mid,res=0;
			while(ll<=rr){
				mid=(ll+rr)>>1;
				if(b[mid]+add[i]<=c) res=mid-l[i],rr=mid-1;
				else ll=mid+1;
			}
			ans+=res;
		}
	}
	return ans+1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
	build_block();
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&op,&x,&y,&k);
		if(op==2) modify(x,y,k);
		else{
			int L=-1e6,R=1e6,mid,ans=-1;
			while(L<=R){
				mid=(L+R)>>1;
				int temp=query(x,y,mid);
				if(temp>=k) ans=mid,R=mid-1;
				else L=mid+1;
			}
			printf("%d\n",ans-1);
		}
	}
	return 0;
}
/*
7 4
-1 2 -5 7 6 -3 1
1 2 5 2
2 3 6 1
2 1 4 2
1 1 7 3

10 6
2 3 5 6 4 4 10 -1 4 6
1 4 9 3
2 1 5 -1
2 3 7 3
1 2 8 4
2 1 10 1
1 1 10 5
*/