分块，吸氧90pts，TLE on #9求调qwq

rt

解释一下几个数组：st_i 是第 i 个块的起点，ed_i 则是终点，a_i 是原数组，id_i 是第 i 个数所在块的编号，delta_i 是第 i 个块的延迟标记，t_i 是用来排序的数组。

预言一波感觉又是犯了很nt的错误

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int N=1e6+5;
int n,q,num;
int st[N],ed[N],a[N],id[N],delta[N],t[N],size[N];
inline void write(int x);
inline int read();
void init();
void add(int l,int r,int c);
int query(int l,int r,int c);
int main(){
    n=read(),q=read();
    getchar();
    for(int i=1;i<=n;i++) a[i]=read();
    getchar();
    while(q--){
        char ch=getchar();
        int L=read(),R=read(),X=read(); 
        if(ch=='M'){
            add(L,R,X);
        }else if(ch=='A'){
            int ans=query(L,R,X);
            write(ans); 
            printf("\n");
        }
        if(q) getchar();
    }
    return 0;
}
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
inline void write(int x){if(x<0)x=~x+1,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');}
void init(){
    num=sqrt(n); 
    for(int i=1;i<=num;i++) st[i]=n/num*(i-1)+1,ed[i]=n/num*i;
    ed[num]=n;
    for(int i=1;i<=num;i++){
        for(int j=st[i];j<=ed[i];j++) id[j]=i;
        size[i]=ed[i]-st[i]+1;
    } 
}
void Sort(int x){
    for(int i=st[x];i<=ed[x];i++) t[i]=a[i];
    sort(t+st[x],t+ed[x]+1);
}
void add(int l,int r,int c){
    int sid=id[l],eid=id[r];
    if(sid==eid){
        for(int i=l;i<=r;i++) a[i]+=c;
        Sort(sid);
        return ;
    }
    for(int i=l;i<=ed[sid];i++) a[i]+=c;
    for(int i=sid+1;i<eid;i++) delta[i]+=c;
    for(int i=st[eid];i<=r;i++) a[i]+=c;
    Sort(sid);
    Sort(eid);
    return ;
}
int query(int l,int r,int c){
    int sid=id[l],eid=id[r],ans=0;
    if(sid==eid){
        for(int i=l;i<=r;i++) ans+=(a[i]+delta[sid]>=c?1:0);
        return ans;
    }
    for(int i=l;i<=ed[sid];i++) ans+=(a[i]+delta[sid]>=c?1:0);
    for(int i=sid+1;i<eid;i++) ans+=(ed[i]-(lower_bound(t+st[i],t+ed[i]+1,c-delta[i])-t)+1);
    for(int i=st[eid];i<=r;i++) ans+=(a[i]+delta[eid]>=c?1:0);
    return ans;
}