救救孩子吧 必关

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,len,a[200010],b[200010],bl[200010],lazy[1010];
inline int left(int k){return (k-1)*len+1;}
inline int right(int k){return min(k*len,n);}
inline void rebuild(int k)
{
	int l=left(k),r=right(k);
	if(l>r)return;
	for(int i=l;i<=r;i++)a[i]=b[i];
	sort(a+l,a+r+1);
}
inline void push_down(int k)
{
	int l=left(k),r=right(k);
	if(l>r)return;
	for(int i=l;i<=r;i++)
	{
		a[i]+=lazy[k];
		b[i]+=lazy[k];
	}
	lazy[k]=0;
}
signed main()
{
	int m,op,l,r,c,x,L,R,mid,ans;
	scanf("%lld",&n);
	m=n,len=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		b[i]=a[i];
		bl[i]=(i-1)/len+1;
	}
	for(int i=1;i<=n/len+1;i++)rebuild(i);
	while(m--)
	{
		scanf("%lld%lld%lld%lld",&op,&l,&r,&c);
		if(!op)
		{
			push_down(bl[l]);
			push_down(bl[r]);
			if(bl[l]==bl[r])
			{
				for(int i=l;i<=r;i++)b[i]+=c;
				rebuild(bl[l]);
			}
			else
			{
				for(int i=l;i<=right(bl[l]);i++)
				{
					b[i]+=c;
					rebuild(bl[l]);
				}
				for(int i=left(bl[r]);i<=r;i++)
				{
					b[i]+=c;
					rebuild(bl[r]);
				}
				for(int i=bl[l]+1;i<bl[r];i++)lazy[i]+=c;
			}
		}
		else
		{
			x=c*c;
			push_down(bl[l]);
			push_down(bl[r]);
			ans=0;
			for(int i=l;i<=right(bl[l]);i++)if(b[i]<x)ans++;
			for(int i=left(bl[r]);i<=r;i++)if(b[i]<x)ans++;
			for(int i=bl[l]+1;i<bl[r];i++)
			{
				L=left(i),R=right(i);
				while(L<=R)
				{
					mid=(L+R)/2;
					if(a[mid]<x-lazy[i])L=mid+1;
					else R=mid-1;
				}
				ans+=(L-left(i));
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}