学步园

分块

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,q,t,m,a[1000001],b[1000001],pos[1000001],add[1000001];
void reset(int x){
	int l=(x-1)*t+1,r=min(x*t,n);
	for(int i=l;i<=r;i++)b[i]=a[i];
	sort(b+l,b+r+1);
}
int find(int x,int v){
	int l=(x-1)*t+1,r=min(x*t,n),last=r;
	while(l<=r){
		int mid=(l+r)>>1;
		if(b[mid]<v)l=mid+1;
		else r=mid-1;
	}
	return last-l+1;
}
void update(int l,int r,int v){
	if(pos[l]==pos[r])
		for(int i=l;i<=r;i++)
			a[i]+=v;
	else{
		for(int i=l;i<=pos[l]*t;i++)a[i]+=v;
		for(int i=(pos[r]-1)*t+1;i<=r;i++)a[i]+=v;
	}
	reset(pos[l]);reset(pos[r]);
	for(int i=pos[l]+1;i<=pos[r]-1;i++)
		add[i]+=v;
}
void ask(int l,int r,int c){
	int sum=0;
	if(pos[l]==pos[r]){
		for(int i=l;i<=r;i++)
			if(a[i]+add[pos[i]]>=c)sum++;
	}
	else{
		for(int i=l;i<=pos[l]*t;i++)
			if(a[i]+add[pos[i]]>=c)sum++;
		for(int i=(pos[r]-1)*t+1;i<=r;i++)
			if(a[i]+add[pos[i]]>=c)sum++;
	}
	for(int i=pos[l]+1;i<=pos[r]-1;i++)
		sum+=find(i,c-add[i]);
	printf("%d\n",sum);
}
int main(){
	n=read();q=read();t=(int)(sqrt(n));
	for(int i=1;i<=n;i++)
		b[i]=a[i]=read(),pos[i]=(i-1)/t+1;
	if(n%t)m=n/t+1;else m=n/t;
    for(int i=1;i<=m;i++)reset(i);
	for(int i=1;i<=q;i++){
		char s[2];
		int l,r,c;
		scanf("%s%d%d%d",s,&l,&r,&c);
		if(s[0]=='A')ask(l,r,c);
		else update(l,r,c);
	}
	return 0;
}