#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, T = 1e3 + 5;
int n, q;
int a[N], b[N];
int l[T], r[T], bl[N], tot, block;
int tag[T];
void build()
{
block = sqrt(n), tot = n / block;
if (n % block != 0)
++tot;
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 <= n; ++i)
bl[i] = (i - 1) / block + 1;
}
void update_part(int L, int R, int K, int p)
{
for (int i = L; i <= R; ++i)
a[i] += K;
memcpy(b + l[p], a + l[p], 8 * (r[p] - l[p] + 1));
}
void update(int L, int R, int K)
{
if (bl[L] == bl[R])
{
update_part(L, R, K, bl[L]);
return;
}
update_part(L, r[bl[L]], K, bl[L]);
update_part(l[bl[R]], R, K, bl[R]);
for (int i = bl[L] + 1; i < bl[R]; ++i)
tag[i] += K;
}
int query_part(int L, int R, int K, int p)
{
int res = 0;
for (int i = L; i <= R; ++i)
res += (a[i] >= K - tag[p]);
return res;
}
int query(int L, int R, int K)
{
if (bl[L] == bl[R])
return query_part(L, R, K, bl[L]);
int res = 0;
res += query_part(L, r[bl[L]], K, bl[L]);
res += query_part(l[bl[R]], R, K, bl[R]);
for (int i = bl[L] + 1; i < bl[R]; ++i)
{
int pos = lower_bound(b + l[i], b + r[i] + 1, K - tag[i]) - b;
res += r[i] - pos + 1;
}
return res;
}
signed main()
{
scanf("%lld%lld", &n, &q);
for (int i = 1; i <= n; ++i)
scanf("%lld", a + i), b[i] = a[i];
build();
for (int i = 1; i <= tot; ++i)
sort(b + l[i], b + r[i] + 1);
while (q--)
{
char op[5];
int x, y, k;
scanf(" %s %lld%lld%lld", &op, &x, &y, &k);
if (op[0] == 'M')
update(x, y, k);
else
printf("%lld\n", query(x, y, k));
}
return 0;
}
100 pts WA on #11 求调
被 Hack 了 awa