题意：n(1e6)个数，m(3e3)个操作，操作分两种，1.把[L,R]内的数加上k 2.询问[L,R]内大于等于k(1e9)的数有多少
分块，每个块内维护顺序序列，复杂度m*sqrt(nlogn)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
#define ll long long
int a[maxn], d[maxn], l[1007], r[1007], lazy[1007], belong[maxn], ans;
int n, q, block, tot, x, y, k;
void build()
{block = sqrt(n);tot = n / block;if (n % block)tot++;for (int i = 1; i <= n; i++)belong[i] = (i - 1) / block + 1, d[i] = a[i];for (int i = 1; i <= tot; i++)l[i] = (i - 1) * block + 1, r[i] = i * block;r[tot] = n;for (int i = 1; i <= tot; i++){sort(d + l[i], d + r[i] + 1);}
}
void change()
{if (belong[x] == belong[y]){for (int i = x; i <= y; i++)a[i] += k;for (int i = l[belong[x]]; i <= r[belong[x]]; i++)d[i] = a[i];sort(d + l[belong[x]], d + r[belong[x]] + 1);}else{for (int i = x; i <= r[belong[x]]; i++)a[i] += k;for (int i = l[belong[x]]; i <= r[belong[x]]; i++)d[i] = a[i];sort(d + l[belong[x]], d + r[belong[x]] + 1);for (int i = l[belong[y]]; i <= y; i++)a[i] += k;for (int i = l[belong[y]]; i <= r[belong[y]]; i++)d[i] = a[i];sort(d + l[belong[x]], d + r[belong[x]] + 1);sort(d + l[belong[y]], d + r[belong[y]] + 1);for (int i = belong[x] + 1; i <= belong[y] - 1; i++)lazy[i] += k;}
}
void query()
{ans = 0;if (belong[x] == belong[y]){for (int i = x; i <= y; i++)if (lazy[belong[x]] + a[i] >= k)ans++;}else{int tt = lower_bound(d + l[belong[x]], d + r[belong[x]] + 1, k - lazy[belong[x]])-d;ans += min(r[belong[x]] - tt + 1, r[belong[x]] - x + 1);tt = lower_bound(d + l[belong[y]], d + r[belong[y]] + 1, k - lazy[belong[y]]) - d;ans += max(y - tt + 1, 0);for (int i = belong[x] + 1; i <= belong[y] - 1; i++){int t1 = lower_bound(d + l[i], d + r[i] + 1, k - lazy[i]) - d;ans += r[i] - t1 + 1;}}cout << ans << endl;
}
int main()
{while (cin >> n >> q){for (int i = 1; i <= n; i++)scanf("%d", &a[i]);build();while (q--){char cz;cin >> cz >> x >> y >> k;if (cz == 'M')change();if (cz == 'A')query();}}
}