90pts，WA了第3个点

Link

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
#define MAXN 100010
using namespace std;
LL n,m,len;
LL a[MAXN];
LL b[MAXN];
LL block[MAXN];
LL L[MAXN],R[MAXN];
LL tag[MAXN];
void update(LL l,LL r,LL k)
{
	if(block[l]==block[r])
	{
		for(LL i=l;i<=r;i++)
			a[i]+=k;
		for(LL i=L[block[l]];i<=R[block[l]];i++)
			b[i]=a[i];
		sort(b+L[block[l]],b+R[block[l]]+1);
		return; 
	}
	for(LL i=l;i<=R[block[l]];i++)
		a[i]+=k;
	for(LL i=L[block[l]];i<=R[block[l]];i++)
		b[i]=a[i];
	sort(b+L[block[l]],b+R[block[l]]+1);
	for(LL i=L[block[r]];i<=r;i++)
		a[i]+=k;
	for(LL i=L[block[r]];i<=R[block[r]];i++)
		b[i]=a[i];
	sort(b+L[block[r]],b+R[block[r]]+1);
	for(LL i=block[l]+1;i<=block[r]-1;i++)
		tag[i]+=k;
}
LL query(LL l,LL r,LL k)
{
	LL res=-1;
	if(block[l]==block[r])
	{
		for(LL i=l;i<=r;i++)
			if(a[i]+tag[block[l]]<k)
				res=max(res,a[i]+tag[block[l]]);
		return res;
	}
	for(LL i=l;i<=R[block[l]];i++)
		if(a[i]+tag[block[l]]<k)
			res=max(res,a[i]+tag[block[l]]);
	for(LL i=L[block[r]];i<=r;i++)
		if(a[i]+tag[block[r]]<k)
			res=max(res,a[i]);
	for(LL i=block[l]+1;i<=block[r]-1;i++)
	{
		LL x=lower_bound(b+L[i],b+R[i]+1,k-tag[i])-b-1;
		if(x>=L[i]&&x<=R[i])
			res=max(res,b[x]+tag[i]);
	}
	return res;
}
int main()
{
	scanf("%lld",&n);
	len=sqrt(n);
	for(LL i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		b[i]=a[i];
		block[i]=(i-1)/len+1;
	}
	m=block[n];
	for(LL i=1;i<=m;i++)
		L[i]=(i-1)*len+1,R[i]=min(i*len,n);
	for(LL i=1;i<=m;i++)
		sort(b+L[i],b+R[i]+1);
	for(LL i=1;i<=n;i++)
	{
		LL op,l,r,c;
		scanf("%lld%lld%lld%lld",&op,&l,&r,&c);
		if(op==0)
			update(l,r,c);
		else
			printf("%lld\n",query(l,r,c));
	}
	return 0;
}