#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int len,bel[MAXN],a[MAXN],p[MAXN],bl[1000],br[1000],lazy[1000],n;
bool cmp(int x,int y)
{
	return a[x]<a[y];
}
void init()
{
	len=sqrt(n)*log2(n);
	for(register int i=1;i<=n/len;i++)
		bl[i]=br[i-1]+1,br[i]=i*len;
	br[n/len]=n;
	for(register int i=1;i<=n/len;i++)
		for(register int j=bl[i];j<=br[i];i++)
			bel[p[j]=j]=i;
	for(register int i=1;i<=n/len;i++)
		sort(p+bl[i],p+br[i]+1,cmp);
}
inline int binary(int l,int r,int k)
{
	long long ans=0;
	if(bel[l]==bel[r])
	{
		for(register int i=l;i<=r;i++)if(a[i]+lazy[bel[l]]<=k)ans++;
		return ans;
	}
	for(register int i=l;i<=br[bel[l]];i++)if(a[i]+lazy[bel[l]]<=k)ans++;//O(len)
	for(register int i=bl[bel[r]];i<=r;i++)if(a[i]+lazy[bel[r]]<=k)ans++;
	for(register int i=bel[l]+1;i<bel[r];i++)
	{
		long long L=bl[i],R=br[i];
		if(a[p[bl[i]]]+lazy[i]>k)continue;
		if(a[p[br[i]]]+lazy[i]<=k)
		{
			ans+=br[i]-bl[i]+1;continue;
		}
		while(L<R)
		{
			long long mid=L+R>>1ll+1;
			if(a[p[mid]]+lazy[i]<=k)L=mid;
			else R=mid-1;
		}
		if(a[p[L]]+lazy[i]<=k)ans+=L-bl[i]+1;
	}// O(n/len *logn)
	return ans;
}
inline int getmin(int l,int r)
{
	int ans=2e9+5;
	if(bel[l]==bel[r])
	{
		for(register int i=l;i<=r;i++)ans=min(ans,a[i]+lazy[bel[l]]);
		return ans;
	}
	for(register int i=l;i<=br[bel[l]];i++)ans=min(ans,a[i]+lazy[bel[l]]);
	for(register int i=bl[bel[r]];i<=r;i++)ans=min(ans,a[i]+lazy[bel[r]]);
	for(register int i=bel[l]+1;i<bel[r];i++)ans=min(ans,a[p[bl[i]]]+lazy[i]);
	return ans;//O(len+n/len)
}
inline int getmax(int l,int r)
{
	int ans=-2e9-5;
	if(bel[l]==bel[r])
	{
		for(register int i=l;i<=r;i++)ans=max(ans,a[i]+lazy[bel[l]]);
		return ans;
	}
	for(register int i=l;i<=br[bel[l]];i++)ans=max(ans,a[i]+lazy[bel[l]]);
	for(register int i=bl[bel[r]];i<=r;i++)ans=max(ans,a[i]+lazy[bel[l]]);
	for(register int i=bel[l]+1;i<bel[r];i++)ans=max(ans,p[a[br[i]]]+lazy[i]);
	return ans;//O(len+n/len)
}
int c1[MAXN],c2[MAXN],t1,t2;
inline void merges(int l,int r,int L,int R)
{
	t1=0;t2=0;
	for(register int i=l;i<=r;i++)(L<=p[i]&&p[i]<=R)?c1[++t1]=a[p[i]]:c2[++t2]=a[p[i]];
	while(t1&&t2)p[r--]=(a[c1[t1]]>a[c2[t2]])?c1[t1--]:c2[t2--];
	while(t1)p[r--]=c1[t1--];
	while(t2)p[r--]=c2[t2--];
}
inline void add(int l,int r,int k)
{
	if(bel[l]==bel[r])
	{
		for(register int i=l;i<=r;i++)a[i]+=k;
		merges(bl[bel[l]],br[bel[l]],l,r);//O(len)
		return;
	}
	for(register int i=l;i<=br[bel[l]];i++)a[i]+=k;
	merges(bl[bel[l]],br[bel[l]],l,br[bel[l]]);//O(len+n/len)
	for(register int i=bl[bel[r]];i<=r;i++)a[i]+=k;
	merges(bl[bel[r]],br[bel[r]],bl[bel[r]],r);
	for(register int i=bel[l]+1;i<bel[r];i++)lazy[i]+=k;
}
inline void query(int l,int r,int k)
{
	if(k<1||k>(r-l+1))
	{
		printf("-1\n");
		return;
	}
	long long L=getmin(l,r),R=getmax(l,r),ans=0;
	while(L<=R)
	{
		long long mid=L+R>>1ll;
		if(binary(l,r,mid)<k)L=mid+1ll;
		else 
		{
			R=mid-1ll;
			ans=mid;
		}
	}//O(logn)
	printf("%lld\n",ans);
}
int main()
{
	int q;scanf("%d%d",&n,&q);
	for(register int i=1;i<=n;i++)scanf("%d",a+i);
	while(q--)
	{
		int opt,l,r,k;scanf("%d%d%d%d",&opt,&l,&r,&k);
		if(opt==1)
		{
			query(l,r,k);
		}
		if(opt==2)
		{
			add(l,r,k);
		}
	}
	return 0;
}

对拍过答案对的

求大佬卡常