神秘TLE，救救孩子

#include <bits/stdc++.h>
typedef long long int64;
#define rg register
char buf[100000],*bus=buf,*but=buf;
#define getchar() (bus==but&&(but=(bus=buf)+fread(buf,1,100000,stdin),bus==but)?EOF:*bus++)
inline int read() {
    register int x(0);
    register char c(getchar());
    while (c<48/*||c>57*/) c=getchar();
    while (c>47/*&&c<58*/) x=(x<<1)+(x<<3)+(c^48), c=getchar();
    return x;
}
template<typename _Tp>
 void write(_Tp x) {
    if (x>9) write(x/10);
    putchar(x%10|48);
}
using namespace std;

#define N 1000030
#define B 5000

int n, q;
int a[N];
int col[N], block_len, half_len, ind(0);
int seq[N];
struct block {
    int l, r, len;
    int add;
} b[B];

int sortT,addT,askT;

inline void sortBlock(const int &i) {
    sort(seq+b[i].l, seq+b[i].r+1);
++sortT;
}

inline void build() {
    n=read(), q=read();
    block_len = 1;
    b[++ind].l=b[ind].r=1,b[ind].len=1;
    seq[1] = a[1] = read();
    for (rg int i(2), j; i<n; ) {
        b[++ind].l = i,
        b[ind].r = min(n, i + block_len - 1),
        b[ind].len = b[ind].r - b[ind].l + 1;
        for (j = 0; j<block_len && i<n; ++j, ++i) {
            seq[i] = a[i] = read();
        }
        sortBlock(ind);
    }
    if(n!=1) seq[n]=a[n]=read(),b[++ind].l=b[ind].r=n,b[ind].len=1;
}

inline void add(const int &blk, const int &w) {
    b[blk].add += w;
}

inline void add(const int &l, const int &r, const int &w) {
    const int lb(col[l]), rb(col[r]);
    if (lb == rb) {
        ++addT;
        for (rg int i(l); i<=r; ++i) a[i] += w;
        sortBlock(lb);
        return;
    }
//  add(l, b[lb].r, w);
//  add(b[rb].l, r, w);
    for (rg int i(l); i<=b[lb].r; ++i) a[i] += w;
        sortBlock(lb);
    for (rg int i(b[rb].l); i<=r; ++i) a[i] += w;
        sortBlock(rb);
    for (rg int i(lb+1); i<rb; ++i) add(i, w);
    ++addT;
}

inline int query(const int &blk, int c) {
    c -= b[blk].add;
++askT;
    return lower_bound(seq+b[blk].l, seq+b[blk].r+1, c) - seq+b[blk].l + 1;
}

inline int query(const int &l, const int &r, int c) {

    const int &lb(col[l]), &rb(col[r]);
    int ans(0);
    if (lb == rb) {
++askT;
        c -= b[lb].add;
        for (rg int i(l); i<=r; ++i)
            if (a[i] >= c) ++ans;
        return ans;
    }
//  ans += query(l, b[lb].r, c);
//  ans += query(b[rb].l, r, c);    
    for (rg int i(l); i<=b[lb].r; ++i)
        if (a[i] + b[lb].add >= c) ++ans;
    for (rg int i(b[rb].l); i<=r; ++i)
        if (a[i] + b[rb].add >= c) ++ans;
    for (rg int i(lb+1); i<rb; ++i)
    {
        //ans += query(i, c);
        c -= b[i].add;
        ans += lower_bound(seq+b[i].l, seq+b[i].r+1, c) - seq+b[i].l + 1 ;
        c += b[i].add;
    }   
    return ans;
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("P2801_8.in", "r", stdin);//freopen("P2801.out", "w", stdout);
#endif
#define debug(x) cout<<#x<<'='<<x<<'\n'
    build();
    rg char opt;
    rg int l, r, k;
    while (q--) {
        opt=0;
        while(opt!='M'&&opt!='A') opt=getchar();
        l=read(), r=read(), k=read();
        if (opt == 'M')
            add(l, r, k);
        else //'A'
        //  query(l, r, k);
            write(query(l, r, k)),putchar('\n');
        //cout<<clock()<<' ';
        //if(q%100==0) cout<<clock()<<'\n',debug(addT),debug(askT),debug(sortT);
    }

//  freopen("CON","w",stdout);

    return 0;
}

www.luogu.com.cn/record/59504443 www.luogu.com.cn/record/59504653 www.luogu.com.cn/record/59471030
3次块长设为1，\sqrt {n}\,,n时间差别却不大，求救