分块维护最小值
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 510,M=200100,P=998274353,INF=0x3f3f3f3f;
int n, m, blo,a,b,c;
int v[N], bl[N], atag[N];
vector<int>ve[N];
void reset(int x)
{
ve[x].clear();
for (int i = (x - 1) * blo + 1; i <= min(x * blo, n); i++)
ve[x].push_back(v[i]);
sort(ve[x].begin(), ve[x].end());
}
void add(int a, int b, int c)
{
for (int i = a; i <= min(bl[a] * blo, b); i++)
v[i] += c;
reset(bl[a]);
if (bl[a] != bl[b])
{
for (int i = (bl[b] - 1) * blo + 1; i <= b; i++)
v[i] += c;
reset(bl[b]);
}
for (int i = bl[a] + 1; i <= bl[b] - 1; i++)
atag[i] += c;
}
int query(int a, int b, int c)
{
int ans = 0;
for (int i = a; i <= min(bl[a] * blo, b); i++)
if (v[i] + atag[bl[a]] < c)
ans++;
if (bl[a] != bl[b])
for (int i = (bl[b] - 1) * blo + 1; i <= b; i++)
if (v[i] + atag[bl[b]] < c)
ans++;
for (int i = bl[a] + 1; i <= bl[b] - 1; i++)
{
int x = c - atag[i];
ans += lower_bound(ve[i].begin(), ve[i].end(), x) - ve[i].begin();
}
return ans;
}
int main()
{
cin >> n >> m;
blo = sqrt(n);
for (int i = 1; i <= n; i++)
cin >> v[i];
for (int i = 1; i <= n; i++)
bl[i] = (i - 1) / blo + 1, ve[bl[i]].push_back(v[i]);
for (int i = 1; i <= bl[n]; i++)
sort(ve[i].begin(), ve[i].end());
for (int i = 1; i <= m; i++)
{
char f; cin >> f;
cin >> a >> b >> c;
if (f == 'M')add(a, b, c);
else cout << b - a + 1 - query(a, b, c) << endl;
}
}