做法一
块内二分。
对每一个元素进行备份并处理增量，查询使用二分。
做法二
暴力枚举+优化即可。
维护一个块内最大值与最小值，记为 (ma_i) 和 (mi_i)。
查询整块时，若 (c^2le mi_i) 则说明没有一个值是 (<c^2) 的，若 (c^2>ma_i) 则说明全都是 (<c^2) 的值。
剩下的暴力即可。
#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int bel[N],bl,num,n;int ans;
int a[N],add[N],mi[N],ma[N];
int read() {
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)) {
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch)) {
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
void build() {
bl=sqrt(n);
memset(mi,0x3f,sizeof mi);
for(int i=1;i<=n;i++) {
bel[i]=(i-1)/bl+1;
ma[bel[i]]=max(ma[bel[i]],a[i]);
mi[bel[i]]=min(mi[bel[i]],a[i]);
}
}
int ask(int l,int r,int c) {
ans=0;
for(int i=l;i<=min(r,bel[l]*bl);i++)
if(a[i]+add[bel[l]]<c)
ans++;
if(bel[l]!=bel[r])
for(int i=(bel[r]-1)*bl+1;i<=r;i++)
if(a[i]+add[bel[r]]<c)
ans++;
for(int i=bel[l]+1;i<=bel[r]-1;i++) {
if(c<=mi[i])
continue;
if(c>ma[i]) {
ans+=bl;
continue;
}//小小优化，能够 AC
for(int j=(i-1)*bl+1;j<=i*bl;j++)
if(a[j]+add[i]<c)
ans++;
}
return ans;
}
void change(int l,int r,int c) {
for(int i=l;i<=min(r,bel[l]*bl);i++) {
a[i]+=c;
mi[bel[i]]=min(a[i]+add[bel[i]],mi[bel[i]]);
ma[bel[i]]=max(a[i]+add[bel[i]],ma[bel[i]]);
}
if(bel[l]!=bel[r])
for(int i=(bel[r]-1)*bl+1;i<=r;i++) {
a[i]+=c;
mi[bel[i]]=min(a[i]+add[bel[i]],mi[bel[i]]);
ma[bel[i]]=max(a[i]+add[bel[i]],ma[bel[i]]);
}
for(int i=bel[l]+1;i<=bel[r]-1;i++) {
add[i]+=c;
mi[i]+=c;
ma[i]+=c;
}//对 mi,ma 进行维护
}
int main() {
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
build();
for(int i=1;i<=n;i++) {
int opt,l,r,c;
opt=read(),l=read(),r=read(),c=read();
if(opt==1)
printf("%d
",ask(l,r,c*c));
else
change(l,r,c);
}
}