只有三十分

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,siz,a[1000005],lazy[1000005],d[1000005];
int get_block(int x){
	return (x-1)/siz+1;
}
int get_start(int x){
	return (x-1)*siz+1;
}
int get_end(int x){
	return min(n,x*siz);
}
void change(int l,int r,int k){
	int ll=get_block(l),rr=get_block(r);
	if(ll==rr){
		for(int i=l;i<=r;i++) a[i]+=k;
		for(int i=get_start(ll);i<=get_end(ll);i++) d[i]=a[i];
		sort(d+get_start(ll),d+1+get_end(ll));
		return; 
	}
	for(int i=l;i<=get_end(ll);i++){
		a[i]+=k;
	}
	for(int i=get_start(ll);i<=get_end(ll);i++){
		d[i]=a[i];
	}
	sort(d+get_start(ll),d+1+get_end(ll));
	for(int i=get_start(rr);i<=r;i++){
		a[i]+=k;
	}
	for(int i=get_start(rr);i<=get_end(rr);i++){
		d[i]=a[i];
	}
	sort(d+get_start(rr),d+1+get_end(rr));
	for(int i=ll+1;i<=rr-1;i++) lazy[i]+=k;
}
int query(int l,int r,int k){
	int ans=0;
	int ll=get_block(l),rr=get_block(r);
	if(ll==rr){
		for(int i=l;i<=r;i++){
			if(lazy[ll]+a[i]>=k) ans++;
		}
		return ans; 
	}
	for(int i=l;i<=get_end(ll);i++) if(lazy[ll]+a[i]>=k) ans++;
	for(int i=get_start(rr);i<=r;i++) if(lazy[rr]+a[i]>=k) ans++;
	for(int i=ll+1;i<=rr-1;i++){
		ans+=get_end(i)-(lower_bound(d+get_start(i),d+1+get_end(i),k-lazy[i])-d)+1;
	}
	return ans;
}
signed main(){
	cin>>n>>q;
	siz=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		d[i]=a[i];
	}
	for(int i=1;i<=get_block(n);i++) sort(a+get_start(i),a+1+get_end(i));
	for(int i=1;i<=q;i++){
		char c;
		int aa,bb,cc;
		cin>>c>>aa>>bb>>cc;
		if(c=='A'){
			cout<<query(aa,bb,cc)<<endl;
		}
		else{
			change(aa,bb,cc);
		}
	}
	return 0;
}