90pts

WA on Sub#0#12 Sub#1#1

#include<bits/stdc++.h>
using namespace std;
int n,a[1000001],s,num,tag[1001];
vector<int> block[1001];
void assign(int x){
    block[x].clear();
    for(int i=(x-1)*s+1;i<=min(n,x*s);++i) block[x].push_back(a[i]);
    sort(block[x].begin(),block[x].end());
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int q;
    cin>>n>>q;
    for(int i=1;i<=n;++i) cin>>a[i];
    s=sqrt(n);
    num=(n-1)/s+1;
    for(int i=1;i<=n;++i){
        block[(i-1)/s+1].push_back(a[i]);
    }
    for(int i=1;i<=num;++i) assign(i);
    while(q--){
        char op;
        int l,r,v;
        cin>>op>>l>>r>>v;
        if(op=='M'){
            int i=l;
            for(;i<=min(r,((l-1)/s+1)*s);++i) a[i]+=v;
            assign((l-1)/s+1);
            if(i>r) continue;
            for(;i<=(r-1)/s*s;i+=s) tag[(i-1)/s+1]+=v;
            for(;i<=r;++i) a[i]+=v;
            assign((r-1)/s+1);
        }
        if(op=='A'){
            int ans=0;
            int i=l;
            for(;i<=min(r,((l-1)/s+1)*s);++i){
                if(a[i]>=v) ++ans;
            }
            for(;i<=(r-1)/s*s;i+=s){
                int x=(i-1)/s+1;
                ans=ans+block[x].end()-lower_bound(block[x].begin(),block[x].end(),v-tag[x]);
            }
            for(;i<=r;++i){
                if(a[i]>=v) ++ans;
            }
            cout<<ans<<'\n';
        }
    }
}