分块求调，救救孩子

rt,WA #1,#9,RE #4-8,30pts

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
using namespace std;
const int N=1000005;
inline void in (int &x){
    int f=1;x=0;char c=getchar();
    while (c>'9'||c<'0'){if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
char op[15];
int n,q,bl,tot,l,r,k;
int a[N],b[N],tag[N],id[N],L[1005],R[1005]; 
inline void init (){
    in (n);in (q);
    bl=(int) (sqrt(n));
    int tot=(int) (n/bl)+(n%bl!=0); 
    for (int i=1;i<=n;++i){
        in (a[i]);b[i]=a[i];
    }
    for (int i=1;i<=n;++i){
        id[i]=(i-1)/bl+1;
    }
    for (int i=1;i<tot;++i){
        L[i]=(i-1)*bl+1;
        R[i]=i*bl; 
    }
    if (n%bl){
        L[tot]=(tot-1)*bl+1;
        R[tot]=n; 
    }
    for (int i=1;i<=tot;++i){
        sort (b+L[i],b+R[i]+1);
    }
}
inline void update (int l,int r,int k){
    if (id[l]==id[r]){
        for (int i=l;i<=r;++i){
            a[i]+=k;b[i]=a[i];
        }
        sort (b+L[id[l]],b+R[id[r]]+1);
        return ;
    }
    for (int i=l;i<=R[l];++i){
        a[i]+=k,b[i]=a[i];
    }
    sort (b+L[id[l]],b+R[id[l]]+1);
    for (int i=r;i>=L[r];--i){
        a[i]+=k;b[i]=a[i];
    }
    sort (b+L[id[r]],b+R[id[r]]+1);
    for (int i=id[l]+1;i<id[r];++i){
        tag[i]+=k;
    }
} 
inline int query (int l,int r,int k){
    int sum=0;
    if (id[l]==id[r]){
        for (int i=l;i<=r;++i){
            sum+=(tag[id[i]]+a[i])>=k;
        }
        return sum;
    }
    for (int i=l;i<=R[id[l]];++i){
        sum+=(tag[id[l]]+a[i])>=k;
    }
    for (int i=r;i>=L[id[r]];--i){
        sum+=(tag[id[r]]+a[i])>=k;
    }
    for (int i=id[l]+1;i<id[r];++i){
        int pos=lower_bound (b+L[i],b+R[i]+1,k-tag[i])-b-L[i];
        sum+=bl-pos; 
    }
    return sum;
}
inline void solve (){
    for (int i=1;i<=q;++i){
        scanf ("%s",op);
        if (op[0]=='M'){
            in (l);in (r);in (k);
            update (l,r,k);
        }
        if (op[0]=='A'){
            in (l);in (r);in (k);
            printf ("%d\n",query (l,r,k));
        }
    }
}
signed main(){
    init ();
    solve ();
    return 0;
}