90分TLE求调

#pragma GCC target("avx")
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<random>
using namespace std;
int n;
int a[1000005],b[1000005];
int block,tot;
int pos[1000005],l[1010],r[1010],tag[1010];
void read(int &x){
    x=0;
    char ch=getchar_unlocked();
    while(!isdigit(ch)){
        ch=getchar_unlocked();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar_unlocked();
    }
    return;
}
void build(){
    block=(int)sqrt(n);
    tot=n/block;
    if(n%block){
        tot++;
    }
    for(int i=1;i<=n;i++){
        pos[i]=(i-1)/n+1;
        b[i]=a[i];
    }
    for(int i=1;i<=tot;i++){
        l[i]=(i-1)*block+1;
        r[i]=i*block;
    }
    r[tot]=n;
    for(int i=1;i<=tot;i++){
        sort(b+l[i],b+r[i]+1);
    }
    return;
}
void modify(int x,int y,int k){
    if(pos[x]==pos[y]){
        for(int i=x;i<=y;i++){
            a[i]+=k;
        }
        for(int i=x;i<=y;i++){
            b[i]=a[i];
        }
        sort(b+l[pos[x]],b+r[pos[x]]+1);
        return;
    }
    for(int i=x;i<=r[pos[x]];i++){
        a[i]+=k;
    }
    for(int i=l[pos[x]];i<=r[pos[x]];i++){
        b[i]=a[i];
    }
    sort(b+l[pos[x]],b+r[pos[x]]+1);
    for(int i=l[pos[y]];i<=y;i++){
        a[i]+=k;
    }
    for(int i=l[pos[y]];i<=r[pos[y]];i++){
        b[i]=a[i];
    }
    sort(b+l[pos[y]],b+r[pos[y]]+1);
    for(int i=pos[x]+1;i<pos[y];i++){
        tag[i]+=k;
    }
    return;
}
int query(int x,int y,int c){
    int ans=0;
    if(pos[x]==pos[y]){
        for(int i=x;i<=y;i++){
            if(a[i]+tag[pos[i]]>=c){
                ans++;
            }
        }
        return ans;
    }
    for(int i=x;i<=r[pos[x]];i++){
        if(a[i]+tag[pos[i]]>=c){
            ans++;
        }
    }
    for(int i=l[pos[y]];i<=y;i++){
        if(a[i]+tag[pos[i]]>=c){
            ans++;
        }
    }
    for(int i=pos[x]+1;i<pos[y];i++){
        int res=0,st=l[i],ed=r[i];
        while(st<=ed){
            int mid=(st+ed)>>1;
            if(b[mid]+tag[mid]>=c){
                res=mid;
                ed=mid-1;
            }else{
                st=mid+1;
            }
        }
        ans+=(r[i]-res+1);
    }
    return ans;
}
int main(){
    int q;
    read(n);
    read(q);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    build();
    while(q--){
        char ch;
        cin>>ch;
        int l,r,k;
        read(l);read(r);read(k);
        if(ch=='M'){
            modify(l,r,k);
        }else if(ch=='A'){
            printf("%d\n",query(l,r,k));
        }
    }
    return 0;
}