分块全RE求调

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#define pii pair<int,int>
using namespace std;
const int N=1e6+10;
int n,q,block,t;
int st[N],ed[N],pos[N];
long long a[N],add[N];

void ini()
{
	t=sqrt(n);
	block=n/t;
	if(n%block)++t;
	for(int i=1;i<=t;++i){st[i]=(i-1)*block+1;ed[i]=i*block;}
	ed[t]=n;
	for(int i=1;i<=t;++i)
	{
		for(int j=st[i];j<=ed[i];++j)pos[j]=i;
		sort(a+st[i],a+ed[i]+1);
	}
}

void change(int l,int r,long long k)
{
	int lp=pos[l],rq=pos[r];
	if(lp==rq)for(int i=l;i<=r;++i)a[i]+=k;
	else
	{
		for(int i=lp+1;i<rq;++i)add[i]+=k;
		change(l,ed[lp],k);change(st[rq],r,k);
	}
}

long long Sum(int l,int r,long long c)
{
	int lp=pos[l],rq=pos[r];
	if(lp==rq)
	{
		int tot=lower_bound(a+l,a+r+1,c-add[lp])-a;
		return r-tot+1;
	}
	else
	{
		long long ans=0;
		for(int i=lp+1;i<rq;++i)
		{
			int tot=lower_bound(a+st[i],a+ed[i]+1,c-add[i])-a;
			ans+=ed[i]-tot+1;
		}
		ans+=Sum(l,ed[lp],c)+Sum(st[rq],r,c);
		return ans;
	}
}

int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;++i)scanf("%lld",&a[i]);ini();
	getchar();
	for(int i=1,l,r;i<=q;++i)
	{
		char ch;
		scanf("%c%d%d",&ch,&l,&r);
		if(ch=='M')
		{
			long long w;
			scanf("%lld",&w);
			change(l,r,w);
		}
		else
		{
			long long c;
			scanf("%lld",&c);
			printf("%lld\n",Sum(l,r,c));
		}
		getchar();
	}
	return 0;
}