40pts分块求助

#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 1919810
#define M 1919
#define int long long
using namespace std;
int left[M],right[M],pos[N],tot,block,n,m,a[N],d[N],tag[M];
void build(){
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    block=sqrt(n);
    tot=n/block;
    if(n%block)++tot;
    for(int i=1;i<=n;i++)pos[i]=(i-1)/block+1,d[i]=a[i];
    for(int i=1;i<=tot;i++){
        left[i]=(i-1)*block+1;
        right[i]=i*block;
    }
    right[tot]=n;
    for(int i=1;i<=tot;i++)sort(d+left[i],d+right[i]+1);
}
void change(int l,int r,int v){
    if(pos[l]==pos[r]){
        for(int i=l;i<=r;i++)a[i]+=v;
        for(int i=left[pos[l]];i<=right[pos[l]];i++)d[i]=a[i];
        sort(d+left[pos[l]],d+right[pos[r]]+1);
    }else{
        for(int i=l;i<=right[pos[l]];i++)a[i]+=v;
        for(int i=left[pos[l]];i<=right[pos[l]];i++)d[i]=a[i];
        sort(d+left[pos[l]],d+right[pos[l]]+1);
        for(int i=left[pos[r]];i<=r;i++)a[i]+=v;
        for(int i=left[pos[r]];i<=right[pos[r]];i++)d[i]=a[i];
        sort(d+left[pos[r]],d+right[pos[r]]+1);
        for(int i=pos[l]+1;i<=pos[r]-1;i++)tag[i]+=v;
    }
}
int query(int l,int r,int v){
    int ans=0;
    if(pos[l]==pos[r]){
        for(int i=l;i<=r;i++)if(a[i]+tag[pos[l]]>=v)++ans;
    }else{
        for(int i=l;i<=right[pos[l]];i++)if(a[i]+tag[pos[l]]>=v)++ans;
        for(int i=left[pos[r]];i<=r;i++)if(a[i]+tag[pos[r]]>=v)++ans;
        for(int i=pos[l]+1;i<=pos[r]-1;i++){
            int le=left[i],ri=right[i],now=0;
            while(le<=ri){
                int mid=(le+ri)>>1;
                //if(a[mid]+tag[pos[mid]]==v){now=right[i]-mid+1;break;}
                if(a[mid]+tag[i]>=v)ri=mid-1,now=right[i]-mid+1;
                else le=mid+1;
            }
            ans+=now;
        }
    }
    return ans;
}
signed main(){
    //freopen("P2801_2.in","r",stdin);
    scanf("%lld%lld",&n,&m);
    build();
    while(m--){
        char s[5];
        int l,r,v;
        scanf("%s%lld%lld%lld",s,&l,&r,&v);
        if(s[0]=='M')change(l,r,v);
        else printf("%lld\n",query(l,r,v));
    }
    return 0;
}