提交记录

#include<bits/stdc++.h>
#define ll long long
#define N 1000010
#define M 10010
#define otto auto
using namespace std;
int a[N],st[M],e[M],det[M],bl[M],t[N];
template <typename Tp>
void read(Tp &x)
{
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')){
        ch=getchar();
    }
    if(ch=='-'){
        fh=-1;ch=getchar();
    }else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
    }
    x*=fh;
}
void fr(char &x)
{
    x=0;while(x!='M'&&x!='A') x=getchar();
}
void Sort(int k)
{
	for(int i=st[k];i<=e[k];i++)
		t[i]=a[i];
	sort(t+st[k],t+e[k]+1);
}
void mdf(int l,int r,int c)
{
	int i,x=bl[l],y=bl[r];
	if(x==y)
	{
		for(i=l;i<=r;i++)
			a[i]+=c;
		Sort(x);
		return;
	}
	for(i=l;i<=e[x];i++)a[i]+=c;
	for(i=st[y];i<=r;i++)a[i]+=c;
	for(i=x+1;i<y;i++)det[i]+=c;
	Sort(x);
	Sort(y); 
}
int asw(int l,int r,int c)
{
	int i,ans=0,x=bl[l],y=bl[r];
	if(x==y)
	{
		for(i=l;i<=r;i++)
			if(a[i]+det[x]>=c)ans++;
		return ans;
	}
	for(i=l;i<=e[x];i++)
		if(a[i]+det[x]>=c)ans++;
	for(i=st[y];i<=r;i++)
		if(a[i]+det[y]>=c)ans++;
	for(i=x+1;i<y;i++)
		ans+=e[i]-(lower_bound(t+st[i],t+e[i]+1,c-det[i])-t)+1;
	return ans;
}
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","r",stdin);
	int i,j,n,q,num,x,y,z;
	char op;
	read(n),read(q);
	num=sqrt(n)+1;
	for(i=1;i<=n;i++)read(a[i]),t[i]=a[i];
	for(i=1;i<=num;i++)
	{
		st[i]=n/num*(i-1)+1;
		e[i]=n/num*i;
	}
	e[num]=n;
	for(i=1;i<=num;i++)
	{
		for(j=st[i];j<=e[i];j++)
			bl[j]=i;
//		sz[i]=e[i]-st[i]+1;
        sort(t+st[i],t+e[i]+1);
	}
	while(q--)
	{
		fr(op);
		read(x),read(y),read(z);
		if(op=='M')
			mdf(x,y,z);
		if(op=='A')
			printf("%d\n",asw(x,y,z));
	}
	return 0;
}