rt,在loj写分块基础3时,样例过了,交上去WA,写法是块内二分,没用STL,用数组排序后二分

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,ghN=320;
int n,block,tot,L[ghN],R[ghN],srt[N],a[N],add[ghN],belong[N];
inline void init()
{
	block=sqrt(n);
	tot=(n-1)/block+1;
	for(int i=1;i<=tot;i++)
		L[i]=R[i-1]+1,R[i]=i*block;
	R[tot]=n;
	for(int i=1;i<=tot;i++)
		for(int j=L[i];j<=R[i];j++)
			belong[j]=i,srt[j]=a[j];
	for(int i=1;i<=tot;i++)
		sort(srt+L[i],srt+R[i]+1);
	return;
}
inline void modify(int l,int r,int c)
{
	if(belong[l]==belong[r])
	{
		for(int i=l;i<=r;i++)
			a[i]+=c;
		int p=belong[l];
		for(int i=L[p];i<=R[p];i++)
			srt[i]=a[i];
		sort(srt+L[p],srt+R[p]+1);
		return;
	}
	int p=belong[l],q=belong[r];
	for(int i=p+1;i<=q-1;i++)
		add[i]+=c;
	for(int i=l;i<=R[p];i++)
		a[i]+=c;
	for(int i=L[p];i<=R[p];i++)
		srt[i]=a[i];
	sort(srt+L[p],srt+R[p]+1);
	for(int i=r;i>=L[q];i--)
		a[i]+=c;
	for(int i=L[q];i<=R[q];i++)
		srt[i]=a[i];
	sort(srt+L[q],srt+R[q]+1);
	return;
}
inline int query(int l,int r,int c)
{
	int ans=INT_MIN;
	if(belong[l]==belong[r])
	{
		int p=belong[l];
		for(int i=l;i<=r;i++)
			if(a[i]+add[p]<c)
				ans=max(ans,a[i]+add[p]);
		return ans;
	}
	int p=belong[l],q=belong[r];
	for(int i=p+1;i<=q-1;i++)
		ans=max(ans,srt[lower_bound(srt+L[i],srt+R[i]+1,c-add[i])-srt-1]+add[i]);
	for(int i=l;i<=R[p];i++)
		if(a[i]+add[p]<c)
			ans=max(ans,a[i]+add[p]);
	for(int i=r;i>=L[q];i--)
		if(a[i]+add[q]<c)
			ans=max(ans,a[i]+add[q]);
	return ans;
}
int main()
{
	clock_t c1=clock();
#ifdef LOCAL
 	freopen("1.in","r",stdin);
 	freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0);
 	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	init();
	while(n--)
	{
		int op,l,r,c;
		cin>>op>>l>>r>>c;
		if(op==0)
			modify(l,r,c);
		else 
		{
			int ans=query(l,r,c);
			if(ans==INT_MIN)cout<<-1<<endl;
			else cout<<ans<<endl;
		}
	}
#ifdef LOCAL
	cerr<<"Time used:"<<clock()-c1<<"ms";
#endif
 	return 0;
}