题目

给出一个长为$n$的数列，以及$n$个操作，操作涉及区间加法，询问区间内小于某个值$x$的元素个数。

输入

第一行输入一个数字$n$ 。

第二行输入$n$个数字，第i个数字为 $a_i$，以空格隔开。

接下来输入$n$行询问，每行输入四个数字 opt、l、r、c，以空格隔开。

若$opt==0$，表示将位于$[l,r]$的之间的数字都加$c$。

若$opt==1$，表示询问$[l,r]$中，小于c*c的数字的个数。

输出

对于每次询问，输出一行一个数字表示答案。

$我的垃圾分块代码$

求调

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,d[50005],pos[1000005];
struct op{
	int x,i;
}a[1000005];
bool cmp(op a,op b){
	return a.x<b.x;
}
signed main(){
	scanf("%lld",&n);
	int kc=sqrt(n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i].x),a[i].i=i;
	for(int i=1;i<=kc+1;i++) sort(a+(i-1)*kc+1,a+min(i*kc,n)+1,cmp);
	for(int i=1;i<=n;i++)pos[a[i].i]=i;
	for(int i=1;i<=n;i++){
		int op,l,r,c;
		scanf("%lld%lld%lld%lld",&op,&l,&r,&c);
		if(!op){
			if(l%kc!=1){
				int rt=min((l-1)/kc*kc+kc,n);
				while(l<=rt&&l<=r)a[pos[l]].x+=c,l++;
				sort(a+rt-kc+1,a+rt+1,cmp);
				for(int j=rt-kc+1;j<=rt;j++) pos[a[j].i]=j;
			}
			while(l+kc-1<=r)d[(l-1)/kc+1]+=c,l+=kc;
			int b=(r-1)/kc+1;
			while(l<=r) a[pos[l]].x+=c,l++;
			sort(a+(b-1)*kc+1,a+min(n,b*kc)+1,cmp);
			for(int j=(b-1)*kc+1;j<=min(n,b*kc);j++) pos[a[j].i]=j;
		}
		else{
			int ans=0;
			if(l%kc!=1){
				int tmp=(l-1)/kc+1;
				while(l<=r&&l<=min(tmp*kc,n)){
					if(a[pos[l]].x+d[tmp]<c*c)ans++;
					l++;
				}
			}
			while(l+kc-1<=r){
				int ll=l,rr=min(l+kc-1,n),w=l-1;
				while(ll<=rr){
					int mid=ll+rr>>1;
					if(a[pos[mid]].x+d[(l-1)/kc+1]<c*c) w=mid,ll=mid+1;
					else rr=mid-1;
				}
				ans+=(w-l+1),l+=kc;
			}
			while(l<=r){
				if(a[pos[l]].x+d[(l-1)/kc+1]<c*c)ans++;
				l++;
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}