求助站外题

#include<bits/stdc++.h>
using namespace std;
const int N=55000;
struct node{
	int l,r,la;
}bl[N];
struct node1{
	int num,wz;
}a[N];
vector<int> v[N];
int n,id,l,r,c;
void update(int x){
	for(int i=0; i<bl[x].r-bl[x].l+1; i++){
		v[x][i]=a[bl[x].l+i].num;
	}
	sort(v[x].begin(),v[x].end());
}
int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++)scanf("%d",&a[i].num);
	int sq=sqrt(n);
	for(int i=1; i<=sq; i++){
		bl[i].l=n/sq*(i-1)+1;
		bl[i].r=n/sq*i;
	}
	bl[sq].r=n;
	for(int i=1; i<=sq; i++){
		for(int j=bl[i].l; j<=bl[i].r; j++)a[j].wz=i,v[i].push_back(a[j].num);
		sort(v[i].begin(),v[i].end());
	}
	for(int i=1; i<=n; i++){
		scanf("%d%d%d%d",&id,&l,&r,&c);
		if(!id){
			if(a[l].wz==a[r].wz)
				for(int j=l; j<=r; j++)a[j].num+=c;
			else{
				for(int j=l; j<=bl[a[l].wz].r; j++)a[j].num+=c;
				for(int j=r; j>=bl[a[r].wz].l; j--)a[j].num+=c;
				for(int j=a[l].wz+1; j<a[r].wz; j++)bl[j].la+=c;
				update(a[l].wz);
				update(a[r].wz);
			}
		}else{
			int ans=0;
			c*=c;
			if(a[l].wz==a[r].wz){
				for(int j=l; j<=r; j++)if(a[j].num+bl[a[j].wz].la<c)ans++;
			}else{
				for(int j=l; j<=bl[a[l].wz].r; j++)if(a[j].num+bl[a[j].wz].la<c)ans++;
				for(int j=r; j>=bl[a[r].wz].l; j--)if(a[j].num+bl[a[j].wz].la<c)ans++;
				for(int j=a[l].wz+1; j<a[r].wz; j++){
					ans+=int(lower_bound(v[j].begin(),v[j].end(),c-bl[j].la)-v[j].begin());
				}
			}
			printf("%d\n",ans);
		}
	}
}