拯救乌干达的可怜儿童

10 9
719 583 321 556 741 430 50 28 326 804
A 1 10 321
M 1 10 101
A 1 10 337
A 1 10 596
M 1 10 511
A 1 10 142
A 1 10 99
A 1 10 88
M 1 10 609

8
8
5
10
10
10

9
9
5
13
13
13

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1000010;
const ll INF=2147483647;
ll num[maxn],n,m,a[maxn],il,ir,det,lim,l[maxn],r[maxn],len,add[maxn];
vector<ll> e;
vector<ll> block[maxn];
char ch;
void update(ll il,ll ir,ll det)
{
	ll pos = num[il];
	if(num[il] != num[ir])
	{
		for(int i = il; i <= r[num[il]];i++)a[i] += det;
		block[num[il]].clear();
		for(int i = l[num[il]];i <= r[num[il]];i++)
		{
			block[num[il]].push_back(a[i]);
		}
		sort(block[num[il]].begin(),block[num[il]].end());
		while(pos != num[ir])
		{
			pos++;
			if(pos != num[ir])add[pos] += det;
		}
		for(int i = l[pos]; i <= ir;i++)a[i] += det;
		block[pos].clear();
		for(int i = l[pos];i <= r[pos];i++)
		{
			block[pos].push_back(a[i]);
		}
		sort(block[pos].begin(),block[pos].end());
	}
	else
	{
		for(int i = il;i <= ir;i++)a[i] += det;
		block[num[il]].clear();
		for(int i = l[num[il]];i <= r[num[il]];i++)
		{
			block[num[il]].push_back(a[i]);
		}
		sort(block[num[il]].begin(),block[num[il]].end());
	}
}
ll que(ll il,ll ir,ll lim)
{
	ll res = 0;
	if(num[il] == num[ir])
	{
		e.clear();
		for(int i = il;i <= ir;i++)e.push_back(a[i] + add[num[il]]);
		sort(e.begin(),e.end());
		res += e.size() - (lower_bound(e.begin(),e.end(),lim) - e.begin());
	}
	else
	{
		e.clear();
		for(int i = il;i <= r[num[il]];i++)e.push_back(a[i] + add[num[il]]);
		sort(e.begin(),e.end());
		res += e.size() - (lower_bound(e.begin(),e.end(),lim) - e.begin());
		ll pos = num[il];
		while(pos != num[ir])
		{
			pos++;
			if(pos != num[ir])
			{
				res += block[pos].size() - (lower_bound(block[pos].begin(),block[pos].end(),lim - add[pos]) - block[pos].begin());
			}
		}
		e.clear();
		for(int i = l[pos];i <= ir;i++)e.push_back(a[i] + add[pos]);
		sort(e.begin(),e.end());
		res += e.size() - (lower_bound(e.begin(),e.end(),lim) - e.begin());
	}
	return res;
}
int main()
{
	cin>>n>>m;
	len = sqrt(n);
	for(int i = 1;i <= n;i++)cin>>a[i];
	for(int i = 1;i <= len;i++)
	{
		l[i] = (i - 1) * len + 1;
		r[i] = i * len;
		for(int j = l[i];j <= r[i];j++)
		{
			num[j] = i;
			block[i].push_back(a[j]);
		}
		sort(block[i].begin(),block[i].end());
	}
	if(r[len] != n)
	{
		l[++len] = r[len - 1] + 1;
		r[len] = n;
		for(int i = l[len];i <= r[len];i++)
		{
			num[i] = len;
			block[len].push_back(a[i]);
		}
		sort(block[len].begin(),block[len].end());
	}
	while(m--)
	{
		cin>>ch>>il>>ir;
		if(ch == 'M')
		{
			cin>>det;
			update(il,ir,det);
		}
		else
		{
			cin>>lim;
			cout<<que(il,ir,lim)<<"\n";
		}
	}
	return 0;
}