题目链接

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=5e4+7;

int a[N];
int L[N],R[N],pos[N],tag[N],s[N],tmp[N];

int n,siz,tot;

inline void build() {
	siz=sqrt(n);
	while(++tot) {
		L[tot]=R[tot-1]+1;
		R[tot]=min(n,siz*tot);
		sort(tmp+L[tot],tmp+1+R[tot]);
		for(int i=L[tot];i<=R[tot];++i)
			pos[i]=tot,s[tot]+=a[i];
		if(R[tot]==n)
			break;
	}
}

inline void Plus(int x,int y,int delta) {
	int l=pos[x],r=pos[y];
	if(l==r)
		for(int i=x;i<=y;++i)
			a[i]+=delta,s[l]+=delta;
	else {
		for(int i=x;i<=R[l];++i)
			a[i]+=delta,s[l]+=delta;
		for(int i=l+1;i<r;++i)
			tag[i]+=delta,s[i]+=delta*(R[i]-L[i]+1);
		for(int i=L[r];i<=y;++i)
			a[i]+=delta,s[r]+=delta;
	}
}

inline int Find(int x,int y,int delta) {
	int l=pos[x],r=pos[y],ans=0;
	if(l==r) {
		for(int i=x;i<=y;++i)
			if(a[i]+tag[l]<delta)
				++ans;
	}
	else {
		for(int i=x;i<=R[l];++i)
			if(a[i]+tag[l]<delta)
				++ans;
		for(int i=l+1;i<r;++i)
			ans+=lower_bound(tmp+L[i],tmp+1+R[i],delta-tag[i])-tmp-L[i];
		for(int i=L[r];i<=y;++i)
			if(a[i]+tag[r]<delta)
				++ans;
	}
	return ans;
}

signed main() {
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",a+i),tmp[i]=a[i];
	build();
	for(int i=1,op,l,r,c;i<=n;++i) {
		scanf("%d%d%d%d",&op,&l,&r,&c);
		if(op)
			printf("%d\n",Find(l,r,c*c));
		else
			Plus(l,r,c);
	}
    return 0;
}