分块20pts求调

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int S = sqrt(N);
struct copy_val {
    int idx, val;
};
bool cmp(copy_val a, copy_val b) {
    return a.val < b.val;
}
bool lower_bound_cmp(const copy_val& a, const copy_val& b) {
    return a.val < b.val;
}
copy_val b[N];
int n, q, block_len, s, a[N], loc[N], bg[S], ed[S], add[S];
void modify(int l, int r, int c) {
    if (loc[l] == loc[r]) {
        for (int i = l; i <= r; i++)
            a[i] += c;
        for (int i = l; i <= r; i++) 
            b[i].val = a[b[i].idx];
//      sum[loc[l]] += c * (r - l + 1);
        sort(b + bg[loc[l]], b + ed[loc[l]], cmp);
    } else {
        for (int i = l; i <= ed[loc[l]]; i++)
            a[i] += c;
        for (int i = l; i <= ed[loc[l]]; i++) 
            b[i].val = a[b[i].idx];
        sort(b + bg[loc[l]], b + ed[loc[l]], cmp);
//      sum[loc[l]] += c * (ed[loc[l]] - l + 1);
        for (int i = bg[loc[r]]; i <= r; i++)
            a[i] += c;
        for (int i = bg[loc[r]]; i <= r; i++)
            b[i].val = a[b[i].idx];
        sort(b + bg[loc[r]], b + ed[loc[r]], cmp);
//      sum[loc[r]] += c * (r - bg[loc[r]] + 1);
        for (int i = loc[l] + 1; i <= loc[r] - 1; i++)
            add[i] += c;
    }
    return;
}
int query(int l, int r, int c) {
    int ans = 0;
    if (loc[l] == loc[r]) {
        for (int i = l; i <= r; i++)
            if (a[i] + add[loc[l]] >= c) ans++;
    } else {
        for (int i = l; i <= ed[loc[l]]; i++)
            if (a[i] + add[loc[l]] >= c) ans++;
        for (int i = bg[loc[r]]; i <= r; i++)
            if (a[i] + add[loc[r]] >= c) ans++;
        for (int i = loc[l] + 1; i <= loc[r] - 1; i++) {
            copy_val ct;
            ct.idx = 0;
            ct.val = c;
            int pos = lower_bound(b + bg[i], b + ed[i], ct, lower_bound_cmp) - b - bg[i];
            ans += (ed[i] - bg[i] + 1) - pos;
        }
    }
    return ans;
}
int main() {
    cin >> n >> q;
    block_len = sqrt(n);
    s = ceil(1.000 * n / block_len);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i].idx = i;
        b[i].val = a[i];
        loc[i] = ceil(1.000 * i / block_len);
//      cout << loc[i] << ' ';
    }
//  puts("");
    for (int i = 1; i <= s; i++) {
        bg[i] = (i - 1) * block_len + 1;
        ed[i] = i * block_len;
    }
    ed[s] = n;
    for (int i = 1; i <= s; i++) {
        sort(b + bg[i], b + ed[i], cmp);
    }
    char opt;
    int l, r, c;
    while (q--) {
        cin >> opt >> l >> r >> c;
        if (r < l) swap(l, r);
        if (opt == 'M') {
            modify(l, r, c);
        } else if (opt == 'A'){
            cout << query(l, r, c) << '\n';
        }
    }   
    return 0;
}
/*
1 2 3 | 4 5 6 | 7 8 9 | 10 11
*/