求助站外题 数列分块入门2

#include<iostream>
#include<cmath> 
#include<algorithm>
#define int long long
using namespace std;
int n,a[100001],ave,bel[100001],b[1001],cnt,len[1001];
signed main()
{
	cin>>n;
	ave=sqrt(n);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n/ave;i++)
	{
		for(int j=(i-1)*ave+1;j<=i*ave;j++) bel[j]=i;
		len[i]=ave;
	} 
	for(int j=(n/ave)*ave+1;j<=n;j++) bel[j]=n/ave+1;
	len[n/ave+1]=n-(n/ave)*ave;
	cnt=bel[n];
	//块i是[(i-1)*sqrt(n)+1,i*sqrt(n)] 
	//处理块，len是块长
	for(int i=1;i<=cnt;i++)
	{
		sort(a+(i-1)*ave+1,a+(i-1)*ave+len[i]+1);
	}//排序 
	for(int ll=1;ll<=n;ll++)
	{
		int opt,l,r,c;
		cin>>opt>>l>>r>>c;
		if(!opt)
		{
			if(bel[l]==bel[r]) 
			{
				for(int i=l;i<=r;i++) a[i]+=c;
				continue ;
			}
			for(int i=l;i<=bel[l]*ave;i++) a[i]+=c;
			sort(a+(bel[l]-1)*ave+1,a+(bel[l]-1)*ave+len[l]+1);
			for(int i=bel[l]+1;i<=bel[r]-1;i++) b[i]+=c;
			for(int i=(bel[r]-1)*ave+1;i<=r;i++) a[i]+=c;
			sort(a+(bel[r]-1)*ave+1,a+(bel[r]-1)*ave+len[r]+1);
		}else
		{
			c=c*c;
			int ans=0;
			if(bel[l]==bel[r]) 
			{
				for(int i=l;i<=r;i++) if(a[i]+b[bel[i]]<c) ans++;
				cout<<ans<<endl;
				continue ;
			}
			for(int i=l;i<=bel[l]*ave;i++) if(a[i]+b[bel[i]]<c) ans++;
			for(int i=bel[l]+1;i<=bel[r]-1;i++) ans+=lower_bound(a+(i-1)*ave+1,a+(i-1)*ave+len[i]+1,c)-a-1;
			for(int i=(bel[r]-1)*ave+1;i<=r;i++) if(a[i]+b[bel[i]]<c) ans++;
			cout<<ans<<endl;
		}
	}
	return 0;
}