LOJ题面

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

输入格式
第一行输入一个数字 n。

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

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

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

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

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

样例
样例输入
4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2
样例输出
3
0
2
数据范围与提示

对于 100% 的数据，1≤n≤50000、−231≤others、ans≤−231−1。

内存限制：256 MB

时间限制：500 ms

#include<bits/stdc++.h>
#define int long long
#define N 110000
using namespace std;
int n,m,spa,splx,sply,splz,rot[N];
int kuai,lazy[N];
int s[N];
struct node {
	int son[2],siz,val,key;
} q[N];
void upd(int x) {
	q[x].siz=q[q[x].son[0]].siz+q[q[x].son[1]].siz+1;
}
int new_root(int value,int fn) {
	q[fn].siz=1,q[fn].val=value,q[fn].key=rand(),q[fn].son[0] = q[fn].son[1] = 0;
	return fn;
}
int merge(int x,int y) { //x < y
	if(!x||!y) return x+y;
	if(q[x].key<q[y].key) {
		q[x].son[1]=merge(q[x].son[1],y),upd(x);
		return x;
	} else {
		q[y].son[0]=merge(x,q[y].son[0]),upd(y);
		return y;
	}
}
void split(int now,int k,int &x,int &y) {
	if(!now) x=y=0;
	else {
		if(q[now].val<=k) x=now,split(q[now].son[1],k,q[now].son[1],y);
		else y=now,split(q[now].son[0],k,x,q[now].son[0]);
		upd(now);
	}
}
void ins(int us,int fn,int &root) {
	split(root,us,splx,sply),root=merge(merge(splx,new_root(us,fn)),sply);
}
int shan(int us,int &root) {
	split(root,us,splx,sply),split(splx,us-1,splx,splz);
	int Ans = splz;
	splz = merge(q[splz].son[0],q[splz].son[1]);
	root=merge(merge(splx,splz),sply);
	return Ans;	
}
int fkth(int us,int &root) {
	split(root,us-1,splx,sply);
	int Ans = q[splx].siz;
	root=merge(splx,sply);
	return Ans;
}
void kbj(int us,int &kz,int &ky) {
	kz = kuai*(us-1) + 1;
	ky = min(n,kuai*us);
} 
signed main() {
	srand(1919810);
	int opt,cini,L,R,C;
	scanf("%lld",&n),m=n,kuai=sqrt(n);
	for(int i = 1; i <= n; i++) scanf("%lld",&s[i]),ins(s[i],i,rot[(i+kuai-1)/kuai]);
	while(m--) {
		scanf("%lld%lld%lld%lld",&opt,&L,&R,&C);
		if(opt == 1) {
			int Ans = 0;
			for(int i = 1; i <= (n+kuai-1)/kuai; i++) {
				int ned = C*2-lazy[i];
				int fL,fR;
				kbj(i,fL,fR);
				if(fR<L) continue;
				if(fL>R) continue;
				if(fL>=L&&fR<=R) {
					Ans += fkth(ned,rot[i]);					
					continue;
				}
				if(fL<L)
					for(int j = L; j <= fR; j++) Ans += (s[j] < ned);
				else 
					for(int j = fL; j <= R; j++) Ans += (s[j] < ned);
			}
			printf("%lld\n",Ans);
		}
		else {
			for(int i = 1; i <= (n+kuai-1)/kuai; i++) {
				int fL,fR;
				kbj(i,fL,fR);
				if(fR<L) continue;
				if(fL>R) continue;
				if(fL>=L&&fR<=R) {
					lazy[i] += C;					
					continue;
				}
				if(fL<L)
					for(int j = fL; j <= R; j++) {
						int mmp = shan(s[j],rot[i]);
						s[j] += C , ins(s[j],mmp,rot[i]);
					}
				else 
					for(int j = fL; j <= R; j++) {
						int mmp = shan(s[j],rot[i]);
						s[j] += C , ins(s[j],mmp,rot[i]);
					}
			}
		}
	}
	return 0;
}