分块入门3 30pts

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100005;
int n,a[N],cl[N],cr[N],tag[N],C[N];
vector<int> v[(int)sqrt(N)];
inline void build()
{
	int B=sqrt(n);
	for(int k=1;k<=(n/B==0?n/B:n/B+1);k++)
	{
		for(int i=(k-1)*B+1;i<=min(n,k*B);i++)
		{
			cl[i]=(k-1)*B;
			cr[i]=min(n,k*B);
			tag[i]=k;
			v[k].push_back(a[i]);
		}
		sort(v[k].begin(),v[k].end());
	}
	return ;
}
inline void add_on(int l,int r,int c)
{
	if(tag[l]==tag[r])
	{
		for(int i=l;i<=r;i++)
			a[i]+=c;
		v[tag[l]].resize(0);
		for(int i=cl[l];i<=cr[l];i++)
		{
			v[tag[l]].push_back(a[i]);
		}
		sort(v[tag[l]].begin(),v[tag[l]].end());
	}
	else
	{
		for(int i=l;i<=cr[l];i++)
			a[i]+=c;
		v[tag[l]].resize(0);
		for(int i=cl[l];i<=cr[l];i++)
		{
			v[tag[l]].push_back(a[i]);
		}
		sort(v[tag[l]].begin(),v[tag[l]].end());
		for(int i=cl[r];i<=r;i++)
			a[i]+=c;
		v[tag[r]].resize(0);
		for(int i=cl[r];i<=cr[r];i++)
		{
			v[tag[r]].push_back(a[i]);
		}
		sort(v[tag[r]].begin(),v[tag[r]].end());
		for(int i=tag[l]+1;i<=tag[r]-1;i++)
			C[i]+=c;
	}
}
inline void query(int l,int r,int c)
{
	int last=-1;
	if(tag[l]==tag[r])
	{
		for(int i=l;i<=r;i++)
		{
			if(a[i]+C[tag[i]]<c)
			{
				last=max(last,a[i]+C[tag[i]]);
			}
		}
	}
	else
	{
		for(int i=l;i<=cr[l];i++)
		{
			if(a[i]+C[tag[i]]<c)
			{
				last=max(last,a[i]+C[tag[i]]);
			}
		}
		for(int i=cl[r];i<=r;i++)
		{
			if(a[i]+C[tag[i]]<c)
			{
				last=max(last,a[i]+C[tag[i]]);
			}
		}
		for(int i=tag[l]+1;i<=tag[r]-1;i++)
		{
			if(v[i][lower_bound(v[i].begin(),v[i].end(),c-C[i])-v[i].begin()-1]<c&&lower_bound(v[i].begin(),v[i].end(),c-C[i])-v[i].begin()-1>=0)
			{
				last=max(last,v[i][lower_bound(v[i].begin(),v[i].end(),c-C[i])-v[i].begin()-1]+C[i]);
			}
		}
	}
	cout<<last<<endl;
	return ;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build();
	for(int i=1;i<=n;i++)
	{
		int num,l,r,c;
		cin>>num>>l>>r>>c;
		if(num==0)
		{
			add_on(l,r,c);
		}
		else{
			query(l,r,c);
		}
	}
	return 0;
}