题目链接

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=5e4+10;
int n,t,a[N];//t为块数 
int L[N],R[N],pos[N];
int add[N],b[N];

inline void Resort(int p)
{
	for(int i=L[p];i<=R[p];++i)
		b[i]=a[i];
	sort(b+L[p],b+R[p]+1);
}
inline void Init(int n)
{
	t=sqrt(n);
	for(int i=1;i<=t;++i)
	{
		L[i]=(i-1)*t+1;
		R[i]=i*t; 
	}
	if(R[t]<n)L[++t]=R[t-1]+1,R[t]=n;
	for(int i=1;i<=t;++i)
	{
		for(int j=L[i];j<=R[i];++j)
			pos[j]=i;
		Resort(i);
	}
} 
inline void Update(int l,int r,int k)
{
	int pl=pos[l],pr=pos[r];
	if(pl==pr)
	{
		for(int i=l;i<=r;++i)a[i]+=k;
		Resort(pl);
		return;
	}
	for(int i=l;i<=R[pl];++i)
		a[i]+=k;
	Resort(pl);
	for(int i=L[pr];i<=r;++i)
		a[i]+=k; 
	Resort(pr);
	for(int i=pl+1;i<=pr-1;++i)
		add[i]+=k;
} 
inline int Query(int l,int r,int k)
{
	int pl=pos[l],pr=pos[r],ans=0;
	if(pl==pr)
	{
		for(int i=l;i<=r;++i)
			if(a[i]+add[pl]<k)ans++;
		return ans;
	}
	for(int i=l;i<=R[pl];++i)
		if(a[i]+add[pl]<k)ans++;
	for(int i=L[pr];i<=r;++i)
		if(a[i]+add[pr]<k)ans++;
	for(int i=pl+1;i<=pr-1;++i)
	{
		ans+=lower_bound(b+L[i],b+R[i]+1,k-add[i])-b-L[i];
	}
	return ans;
} 

signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&a[i]);
	}
	Init(n);
	for(int i=1;i<=n;++i)
	{
		int opt,l,r,c;
		scanf("%lld%lld%lld%lld",&opt,&l,&r,&c);
		if(opt==0)Update(l,r,c);
		else printf("%lld\n",Query(l,r,c*c));
	} 
	return 0;
}

已经瞪了好久了/kel，违规自删。