第一次分块
分块，将每一个块内部排序
对于A操作，块内部二分查找，两边的零散部分在原数组中暴力查找
对于M操作，给整块打上标记，两边的零散部分暴力修改
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;
LL read() {
LL k = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
k = k * 10 + c - 48, c = getchar();
return k * f;
}
char read_c() {
char c = getchar();
while(c != 'M' && c != 'A') c = getchar();
return c;
}
LL a[1000010], b[1000010], tag[1000010];
int l[1000010], r[1000010], cnt, belong[1000010];
int main() {
//freopen("1.in", "r", stdin);
int n = read(), q = read(), bl = sqrt(n); cnt = (n-1) / bl + 1;
for(int i = 1; i <= n; ++i) {
a[i] = b[i] = read(); int x = (i - 1) / bl + 1;
belong[i] = x;
if(belong[i] != belong[i-1]) l[x] = i, r[x-1] = i-1;
}
l[1] = 1, r[cnt] = n;
//cout << cnt << endl;
for(int i = 1; i <= cnt; ++i) sort(a+l[i], a+r[i]+1);
while(q--) {
//cout << q << endl;
char opt = read_c();
if(opt == 'A') {
int nl = read(), nr = read(); LL k = read();
int pl = belong[nl], pr = belong[nr];
int ans = 0;
if(pl == pr) {
for(int i = nl; i <= nr; ++i) ans += (b[i] >= k-tag[pl]);
printf("%d\n", ans); continue;
}
for(int i = pl+1; i <= pr-1; ++i)
ans += (r[i]-l[i]+1) - (lower_bound(a+l[i], a+r[i]+1, k-tag[i]) - a - l[i]);
if(nl == l[pl]) ans += (r[pl]-l[pl]+1) - (lower_bound(a+l[pl], a+r[pl]+1, k-tag[pl]) - a - l[pl]);
else for(int i = nl; i <= r[pl]; ++i) ans += (b[i] >= k-tag[pl]);
if(nr == r[pr]) ans += (r[pr]-l[pr]+1) - (lower_bound(a+l[pr], a+r[pr]+1, k-tag[pr]) - a - l[pr]);
else for(int i = l[pr]; i <= nr; ++i) ans += (b[i] >= k-tag[pr]);
printf("%d\n", ans);
}
else {
int nl = read(), nr = read(); LL k = read();
int pl = belong[nl], pr = belong[nr];
if(pl == pr) {
for(int i = nl; i <= nr; ++i) b[i] += k;
for(int i = l[pl]; i <= r[pl]; ++i) a[i] = b[i];
sort(a+l[pl], a+r[pr]+1);
}
for(int i = pl+1; i <= pr-1; ++i)
tag[i] += k;
if(nl == l[pl]) tag[pl] += k;
else {
for(int i = nl; i <= r[pl]; ++i) b[i] += k;
for(int i = l[pl]; i <= r[pl]; ++i) a[i] = b[i];
sort(a+l[pl], a+r[pl]+1);
}
if(nr == r[pr]) tag[pr] += k;
else {
for(int i = l[pr]; i <= nr; ++i) b[i] += k;
for(int i = l[pr]; i <= r[pr]; ++i) a[i] = b[i];
sort(a+l[pr], a+r[pr]+1);
}
}
}
return 0;
}