分块板子

真的是个板子……

这里存下，以免以后自己找不到……

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+10;
const int maxtot=1e3+10;

int n,q;
int block,tot;

int a[maxn],d[maxn];
int belong[maxn],lazy[maxtot];
int l[maxtot],r[maxtot];

void build(){
	block=sqrt(n);
	tot=n/block;
	if(n%block)
		tot++;
	for(register int i=1;i<=n;i++){
		belong[i]=(i-1)/block+1;
		d[i]=a[i];
	}
	for(register int i=1;i<=tot;i++){
		l[i]=(i-1)*block+1;
		r[i]=i*block;
	}
	r[tot]=n;
	for(register int i=1;i<=tot;i++)
		sort(d+l[i],d+r[i]+1);
	return;
}

void change(int x,int y,int k){
	if(belong[x]==belong[y]){
		for(register int i=x;i<=y;i++)
			a[i]+=k;
		for(register int i=l[belong[x]];i<=r[belong[x]];i++)
			d[i]=a[i];
		sort(d+l[belong[x]],d+r[belong[x]]+1);
	}
	else{
		for(register int i=x;i<=r[belong[x]];i++)
			a[i]+=k;
		for(register int i=l[belong[x]];i<=r[belong[x]];i++)
			d[i]=a[i];
		sort(d+l[belong[x]],d+r[belong[x]]+1);
		for(register int i=l[belong[y]];i<=y;i++)
			a[i]+=k;
		for(register int i=l[belong[y]];i<=r[belong[y]];i++)
			d[i]=a[i];
		sort(d+l[belong[y]],d+r[belong[y]]+1);
		for(register int i=belong[x]+1;i<=belong[y]-1;i++)
			lazy[i]+=k;
	}
}

int query(int x,int y,int k){
	int ans=0;
	if(belong[x]==belong[y])
		for(register int i=x;i<=y;i++){
			if(lazy[belong[x]]+a[i]>=k)
				ans++;
		}
	else{
		for(register int i=x;i<=r[belong[x]];i++)
			if(lazy[belong[x]]+a[i]>=k)
				ans++;
		for(register int i=l[belong[y]];i<=y;i++)
			if(lazy[belong[y]]+a[i]>=k)
				ans++;
		for(register int i=belong[x]+1;i<=belong[y]-1;i++){
			int ll=l[i],rr=r[i],mid,s=0;
			while(ll<=rr){
				mid=(ll+rr)>>1;
				if(d[mid]+lazy[i]>=k)
					rr=mid-1,s=r[i]-mid+1;
				else
					ll=mid+1;
			}
			ans+=s;
		}
	}
	return ans;
}

int main(){
	char c;
	int l,r,k;
	scanf("%d%d",&n,&q);
	for(register int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build();
	for(register int i=1;i<=q;i++){
		cin>>c;
		scanf("%d%d%d",&l,&r,&k);
		if(c=='M')
			change(l,r,k);
		else
			printf("%d
",query(l,r,k));
	}
	return 0;
}