rt,本代码为 $O(Q\sqrt{n}\log\sqrt{n})$,O2过了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int a[N];
vector<int>block[N];
int L[N],R[N],pos[N],tag[N];
inline void modify(int x)
{
	block[x].clear();
	for(int i=L[x];i<=R[x];++i)
		block[x].push_back(a[i]);
	sort(block[x].begin(),block[x].end());
}
inline void add(int l,int r,int d)
{
	int x=pos[l],y=pos[r];
	if(x==y)
	{
		for(int i=l;i<=r;++i)
			a[i]+=d;
		modify(x);
		return ;
	}
	add(l,R[x],d);
	add(L[y],r,d);
	for(int i=x+1;i<y;++i)
		tag[i]+=d; 
}
inline int query(int l,int r,int d)
{
	int ans=0,x=pos[l],y=pos[r];
	if(x==y)
	{
		for(int i=l;i<=r;++i)
			if(a[i]+tag[x]<d)
				++ans;
		return ans;
	}
	ans=query(l,R[x],d)+query(L[y],r,d);
	for(int i=x+1;i<y;++i)
		ans+=lower_bound(block[i].begin(),block[i].end(),d-tag[i])-block[i].begin();
	return ans;
}
signed main()
{
//	freopen("main.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	int t=sqrt(n);
	for(int i=1;i<=t;++i)
	{
		L[i]=R[i-1]+1;
		R[i]=i*t;
	}
	if(R[t]<n)
	{
		++t;
		L[t]=R[t-1]+1;
		R[t]=n;
	}
	for(int i=1;i<=t;++i)
	{
		modify(i);
		for(int j=L[i];j<=R[i];++j)
			pos[j]=i;
	}
	while(m--)
	{
		char op;
		int l,r,d;
		cin>>op>>l>>r>>d;
		if(op=='M')
			add(l,r,d);
		else
			cout<<r-l+1-query(l,r,d)<<'\n';
	}
}