提交记录

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,T,a[1000005],s[1000005],block[1000005];
int block_l[1005],block_r[1005],add[1005];
void change(int l,int r,int d)
{
	int x_l=block[l],x_r=block[r];
	if(x_l==x_r)
	{
		for(int i=l;i<=r;i++)
		{
			a[i]+=d;
			s[i]=a[i];
		}
		sort(s+block_l[x_l],s+block_r[x_l]+1);
		return;
	}
	if(block_l[x_l]!=l)
	{
		for(int i=l;i<=block_r[x_l];i++)
		{
			a[i]+=d;
			s[i]=a[i];
		}
		sort(s+block_l[x_l],s+block_r[x_l]+1);
		x_l++;
	}
	if(block_r[x_r]!=r)
	{
		for(int i=block_l[x_r];i<=r;i++)
		{
			a[i]+=d;
			s[i]=a[i];
		}
		sort(s+block_l[x_r],s+block_r[x_r]+1);
		x_r--;
	}
	for(int i=x_l;i<=x_r;i++)
	{
		add[i]+=d;
	}
	return;
} 
int ask(int l,int r,int c)
{
	int x_l=block[l],x_r=block[r];
	if(x_l==x_r)
	{
		int cnt=0;
		for(int i=l;i<=r;i++)
		{
			cnt+=(a[i]+add[x_l])>=c;
		}
		return cnt;
	}
	int cnt=0;
	if(l!=block_l[x_l])
	{
		for(int i=l;i<=block_r[x_l];i++)
		{
			cnt+=(a[i]+add[x_l])>=c;
		}
		x_l++;
	}
	if(r!=block_r[x_r])
	{
		for(int i=block_l[x_r];i<=r;i++)
		{
			cnt+=(a[i]+add[x_r])>=c;
		}
		x_r--;
	}
	for(int i=x_l;i<=x_r;i++)
	{
		int ll=block_l[i]-1,rr=block_r[i]+1;
		while(ll+1!=rr)
		{
			int mid=(ll+rr)>>1;
			if(s[mid]+add[i]>=c)rr=mid;
			else ll=mid;
		}
		if(rr==block_r[i]+1)continue;
		cnt+=block_r[i]-rr;
	}
	return cnt;
}
int main()
{
	scanf("%d%d",&n,&T);
	int t=sqrt(n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=t;i++)
	{
		block_l[i]=t*(i-1)+1;
		block_r[i]=t*i;
		for(int j=block_l[i];j<=block_r[i];j++)
		{
			s[j]=a[j];
			block[j]=i;
		}
		sort(s+block_l[i],s+block_r[i]+1);
	}
	if(block_r[t]!=n)
	{
		block_l[t+1]=t*t+1;
		block_r[t+1]=n;
		for(int j=block_l[t+1];j<=block_r[t+1];j++)
		{
			s[j]=a[j];
			block[j]=t+1;
		}
		sort(s+block_l[t+1],s+block_r[t+1]+1);		
	}
	while(T--)
	{
		char c;
		cin>>c;
		if(c=='M')
		{
			int l,r,w;
			scanf("%d%d%d",&l,&r,&w);
			change(l,r,w);
		}
		else
		{
			int l,r,c;
			scanf("%d%d%d",&l,&r,&c);
			printf("%d\n",ask(l,r,c));
		}
	} 
	return 0;
}