lijianyangyf @ 2018-05-13 15:32:54
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
struct B
{
int id;
long long val;
};
struct node
{
int size;
long long C;
B num[1001];
int find_bl(long long x,int l,int r);
int find(long long x);
void add(long long x,int l,int r);
void Bsort();
}a[1001];
void scan();
bool cmp(B x,B y){return x.val<y.val;}
void node::Bsort(){sort(num+1,num+size+1,cmp);}
void node::add(long long x,int l,int r)
{
for(int i=1;i<=size;i++)
if(num[i].id>=l&&num[i].id<=r)
num[i].val+=x;
sort(num+1,num+size+1,cmp);
}
int node::find(long long x)
{
int l=1,r=size;
while(l<r)
{
int mid=(l+r)/2;
if(num[mid].val<x)l=mid+1;
else r=mid-1;
}
while(num[l].val<x)
{
l++;
if(l==size+1)
return 0;
}
while(num[l].val>=x)
{
l--;
if(l==0)
return size;
}
return size-l;
}
int node::find_bl(long long x,int l,int r)
{
int ans=0;
for(int i=1;i<=size;i++)
if(num[i].id>=l&&num[i].id<=r)
if(num[i].val>=x)
ans++;
return ans;
}
int bol;
int n,m;
bool bl;
int main()
{
// freopen("read.in","r",stdin);
scan();
while(m--)
{
char st;int l,r,kl,kr;
long long c;
do{scanf("%c",&st);}while(st=='\n');
scanf("%d%d%lld",&l,&r,&c);
if(!bl)
{
kl=l/bol;
kr=r/bol;
}
else
{
kl=l/(bol-1);
kr=r/(bol-1);
}
kl++;kr++;
if(st=='A')
{
int ans=0;
if(kl==kr)ans+=a[kl].find_bl(c,l,r);
else
{
ans+=a[kl].find_bl(c,l,r);
ans+=a[kr].find_bl(c,l,r);
for(int i=kl+1;i<kr;i++)
ans+=a[i].find(c-a[i].C);
}
printf("%d\n",ans);
}
else
{
if(kl==kr)a[kl].add(c,l,r);
else
{
a[kl].add(c,l,r);
a[kr].add(c,l,r);
for(int i=kl+1;i<kr;i++)
a[i].C+=c;
}
}
}
}
void scan()
{
scanf("%d%d",&n,&m);
bol=sqrt(n);
for(int i=1;i<=bol;i++)
{
a[i].size=bol;
for(int j=1;j<=bol;j++)
{
scanf("%d",&a[i].num[j].val);
a[i].num[j].id=(i-1)*bol+j;
}
sort(a[i].num+1,a[i].num+bol+1,cmp);
}
int l=n-bol*bol;
a[bol+1].size=l;
for(int i=1;i<=l;i++)
{
scanf("%d",&a[bol+1].num[i].val);
a[bol+1].num[i].id=i+bol*bol;
}
if(a[bol+1].size>0)
{
sort(a[bol+1].num+1,a[bol+1].num+l+1,cmp);
bl=1;
bol++;
}
}