P2801 教主的魔法求调

我几乎把所有知道的卡常方法全部用上了，然而……TLE*2

#include <bits/stdc++.h>
#define rint register int
using namespace std;
const int N = 1e6 + 10, sqN = 1e3 + 10;
int n, q, a[N];

//FastSort
int tmp[N], cnt[65540];
inline void RadixSort(int data[], int len){
    for (rint i = 0; i <= 0xffff; ++i) cnt[i] = 0;
    for (rint i = 0; i < len; ++i) cnt[data[i] & 0xffff]++;
    for (rint i = 1; i <= 0xffff; ++i) cnt[i] += cnt[i - 1];
    for (rint i = len - 1; i >= 0; --i){
        int k = data[i] & 0xffff;
        tmp[cnt[k] - 1] = data[i];
        cnt[k]--;
    }

    for (rint i = 0; i <= 0xffff; ++i) cnt[i] = 0;
    for (rint i = 0; i < len; ++i) cnt[tmp[i] >> 16]++;
    for (rint i = 1; i <= 0xffff; ++i) cnt[i] += cnt[i - 1];
    for (rint i = len - 1; i >= 0; --i){
        int k = tmp[i] >> 16;
        data[cnt[k] - 1] = tmp[i];
        cnt[k]--;
    }
}

//Block
int L[sqN], R[sqN], tag[sqN], bel[N], h[N];

inline void init(){
    int len = sqrt(n);
    for (rint i = 1; i <= len; ++i) L[i] = n / len * (i - 1) + 1, R[i] = n / len * i;
    R[len] = n;
    for (rint i = 1; i <= len; ++i){
        for (rint j = L[i]; j <= R[i]; ++j){
            bel[j] = i;
            h[j] = a[j];
        }
        RadixSort(h + L[i], R[i] - L[i] + 1);
    }
}

inline void Sort(int k){
    for (rint i = L[k]; i <= R[k]; ++i) h[i] = a[i];
    RadixSort(h + L[k], R[k] - L[k] + 1);
}

inline void modify(int l, int r, int w){
    int x = bel[l], y = bel[r];
    if (x == y){
        for (rint i = l; i <= r; ++i) a[i] += w;
        Sort(x);
        return;
    }
    for (rint i = l; i <= R[x]; ++i) a[i] += w;
    for (rint i = L[y]; i <= r; ++i) a[i] += w;
    for (rint i = x + 1; i < y; ++i) tag[i] += w;
    Sort(x); Sort(y);
}

inline int query(int l, int r, int c){
    int x = bel[l], y = bel[r], ans = 0;
    if (x == y){
        int goal = c - tag[x];
        for (rint i = l; i <= r; ++i) if (a[i] >= goal) ans++;
        return ans;
    }
    int goal_1 = c - tag[x], goal_2 = c - tag[y];
    for (rint i = l; i <= R[x]; ++i) if (a[i] >= goal_1) ans++;
    for (rint i = L[y]; i <= r; ++i) if (a[i] >= goal_2) ans++;
    for (rint i = x + 1; i < y; ++i) ans += R[i] - (lower_bound(h + L[i], h + R[i] + 1, c - tag[i]) - h) + 1;
    return ans;
}

//Fast read and write
inline int read(){
    int x = 0;
    bool pos = true;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') pos = false;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    return pos ? x : ~(x - 1);
}

char ch[20];
inline void write(int x){
    if (!x) {putchar('0'); return;}
    if (x < 0) x = ~(x - 1);
    int t = 0;
    while (x) ch[++t] = (char)(x % 10 + '0'), x /= 10;
    for (rint i = t; i; --i) putchar(ch[i]);
}

int main(){
    //freopen("test.in", "r", stdin);

    n = read(), q = read();
    for (rint i = 1; i <= n; ++i) a[i] = read();
    for (rint i = 1; i <= q; ++i){
        char op = getchar();
        for (; !isalpha(op); op = getchar());
        int l = read(), r = read(), w = read();
        if (op == 'M') modify(l, r, w);
        else if (op == 'A') write(query(l, r, w)), putchar('\n');
    }
    return 0;
}