题目传送门

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long 
#define MAXN 50010
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)
{
	for(LL i=l;i<=min(R[block[l]],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);
	if(block[l]==block[r])
		return;
	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=0;
	for(LL i=l;i<=min(R[block[l]],r);i++)
		if(a[i]+tag[block[l]]<k)
			res++;
	if(block[l]==block[r])
		return res;
	for(LL i=L[block[r]];i<=r;i++)
		if(a[i]+tag[block[r]]<k)
			res++;
	for(LL i=block[l]+1;i<=block[r]-1;i++)
		res+=lower_bound(b+L[i],b+R[i]+1,k-tag[i])-b-L[i];
	return res;
}
int main()
{
	scanf("%lld",&n);
	len=sqrt(n);
	m=len;
	for(LL i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		b[i]=a[i];
		block[i]=(i-1)/len+1;
	}
	for(LL i=1;i<=m;i++)
		L[i]=(i-1)*len+1,R[i]=i*len;
	if(m*len<n)
	{
		m++;
		L[m]=(m-1)*len+1;
		R[m]=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*c));
	}
	return 0;
}