分块，对于每一个块，排个序
就可以了
#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<stack>
#include<algorithm>
#define int long long
using namespace std;
template<class T>inline void read(T &x)
{
x=0;register char c=getchar();register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=-x;
}
template<class T>inline void print(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar('0'+x%10);
}
int n;
int a[5000001];
int tem[5000001];
int l[5000001];
int r[5000001];
int be[500001];
int cop[5000001];
int len;
int num;
int f;
int x,y,z;
int tag[5000001];
void reini(int x){
for(int i=l[x];i<=r[x];++i){
cop[i]=a[i]+tag[x];
a[i]+=tag[x];
}
tag[x]=0;
sort(cop+l[x],cop+r[x]+1);
}
void add(int ll,int rr,int k){
if(be[ll]==be[rr]){
for(int i=ll;i<=rr;++i){
a[i]+=k;
}
reini(be[ll]);
}else{
for(int i=ll;i<=r[be[ll]];++i){
a[i]+=k;
}
reini(be[ll]);
for(int i=be[ll]+1;i<be[rr];++i){
tag[i]+=k;
}
for(int i=l[be[rr]];i<=rr;++i){
a[i]+=k;
}
reini(be[rr]);
}
}
int que(int ll,int rr,int k){
int ans=0;
if(be[ll]==be[rr]){
for(int i=ll;i<=rr;++i){
if(a[i]+tag[be[ll]]<k)
ans++;
}
return ans;
}else{
for(int i=ll;i<=r[be[ll]];++i){
if(a[i]+tag[be[ll]]<k)
ans++;
}
for(int i=l[be[rr]];i<=rr;++i){
if(a[i]+tag[be[rr]]<k)
ans++;
}
for(int i=be[ll]+1;i<be[rr];++i){
ans+=lower_bound(cop+l[i],cop+r[i]+1,k-tag[i])-cop-l[i];
}
return ans;
}
return ans;
}
signed main(){
read(n);
for(int i=1;i<=n;++i){
read(a[i]);
}
int len=sqrt(n);
num=n/len;
if(n%len) num++;
for(int i=1;i<=n;++i){
be[i]=(i-1)/len+1;
}
for(int i=1;i<=num;++i){
l[i]=(i-1)*len+1;
r[i]=(i)*len;
}
r[num]=n;
for(int i=1;i<=num;++i){
reini(i);
}
for(int i=1;i<=n;++i){
read(f);
if(f==0){
read(x);read(y);read(z);
add(x,y,z);
}else{
read(x);read(y);read(z);
printf("%lld\n",que(x,y,z*z));
}
}
return 0;
}