P13977

主要讲一下代码细节，对于数据结构的原理请去看模板。

Solution

首先有两种操作，区间查询和区间加法，先说说加法。

首先判断 $l,r$ 是不是在一个块里，如果是就直接处理。
否则先把两端多出来的部分处理掉，让 $l,r$ 刚好到达块的端点，然后把中间的整块的懒标记加上 $c$ 就好了。

接下来是区间查询有多少个小于等于 $c^2$ 的个数，显然因为每次的查询不一样，是没有办法一直在线维护的。
所以这个数据给的很极限，我们可以在修改之后还排序，这样查询就很方便了。
所以还是一样先处理两边，因为加法之后会影响顺序，所以需要重新排序，然后查询的时候直接二分一下位置就可以了。

具体实现细节请看代码，个人认为应该容易看懂。

Code

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
LL n,a[500005],lazy[500005],len,L[500005];
vector<LL> v[50005];
inline LL get(LL x){
	return x/len+1;
}
void resort(LL x){
	int i=L[x];v[x].clear();
	while(get(i)==x&&i<=n) v[x].push_back(a[i++]);
	sort(v[x].begin(),v[x].end());
}
void update(LL l,LL r,LL c){
	if(get(l)==get(r)){
		for(int i=l;i<=r;i++) a[i]+=c;
		resort(get(l));
	}else {
		int i=l,j=r;
		while (get(i) == get(l)) a[i++] += c;
		while (get(j) == get(r)) a[j--] += c;
		resort(get(l));resort(get(r));
		for (int k = get(i);k <= get(j);k++) lazy[k] += c;
	}
}
LL query(LL l,LL r,LL c){
	LL res=0;
	if(get(l)==get(r)){
		for(int i=l;i<=r;i++){
			if(a[i]+lazy[get(i)]<c) res++;
		}
	}
	else{
		int i=l,j=r;
		while(get(i)==get(l)) if(a[i++]+lazy[get(l)]<c) res++;
		while(get(j)==get(r)) if(a[j--]+lazy[get(r)]<c) res++;
		for (int k = get(i);k <= get(j);k++) {
			res += lower_bound(v[k].begin(), v[k].end(), c - lazy[k]) - v[k].begin();
		}
	}
	return res;
}
int main(){
	cin>>n;
	len=int(sqrt(n));
	memset(L,0x3f,sizeof(L));
	for(LL i=1;i<=n;i++){
		cin>>a[i];
		LL x=get(i);
		L[x]=min(L[x],i);
		v[x].push_back(a[i]); 
	}
	for(int i=1;i<=n/len;i++) sort(v[i].begin(),v[i].end());
	for(int i=1;i<=n;i++){
		LL l,r,c,op;
		cin>>op>>l>>r>>c;
		if(op) cout<<query(l,r,c*c)<<endl;
		else{
			update(l,r,c);
		}
	}
	return 0;
}