#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define MP make_pair
#define PB push_back
using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
template<typename T>
using vec = vector<T>;
template<typename T, int N>
using arr = array<T, N>;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
const ll INF = 1e18;
const int MOD = 998244353;
int N, M;
vec<int> h, t_min, t_max, lazy;
void build(int l = 1, int r = N, int k = 1)
{
if (l == r)
{
t_min[k] = t_max[k] = h[l];
return;
}
int m = (l + r) / 2;
build(l, m, k * 2);
build(m + 1, r, k * 2 + 1);
t_max[k] = max(t_max[k * 2], t_max[k * 2 + 1]);
t_min[k] = min(t_min[k * 2], t_min[k * 2 + 1]);
}
void push(int k)
{
t_min[k * 2] += lazy[k];
t_min[k * 2 + 1] += lazy[k];
t_max[k * 2] += lazy[k];
t_max[k * 2 + 1] += lazy[k];
lazy[k * 2] += lazy[k];
lazy[k * 2 + 1] += lazy[k];
lazy[k] = 0;
}
void update(int ql, int qr, int l = 1, int r = N, int k = 1)
{
if (l > qr || r < ql) return;
if (l >= ql && r <= qr)
{
t_min[k]++;
t_max[k]++;
lazy[k] = 1;
return;
}
push(k);
int m = (l + r) / 2;
update(ql, qr, l, m, k * 2);
update(ql, qr, m + 1, r, k * 2 + 1);
t_max[k] = max(t_max[k * 2], t_max[k * 2 + 1]);
t_min[k] = min(t_min[k * 2], t_min[k * 2 + 1]);
}
int query1(int x, bool lr, int l = 1, int r = N, int k = 1)
{
if (l == r)
{
if (lr == 0) return (t_max[k] >= x ? l : -1);
else return (t_min[k] <= x ? l : -1);
}
push(k);
int m = (l + r) / 2;
if (lr == 0)
{
if (t_max[k * 2] >= x)
return query1(x, lr, l, m, k * 2);
else return query1(x, lr, m + 1, r, k * 2 + 1);
}
else {
if (t_min[k * 2 + 1] <= x)
return query1(x, lr, m + 1, r, k * 2 + 1);
else return query1(x, lr, l, m, k * 2);
}
}
int query2(int p, int l = 1, int r = N, int k = 1)
{
if (l > p || r < p) return -1;
if (l == r && r == p) return t_min[k];
push(k);
int m = (l + r) / 2;
int a = query2(p, l, m, k * 2);
int b = query2(p, m + 1, r, k * 2 + 1);
return (a == -1 ? b : a);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
h = vec<int>(N + 1);
t_min = t_max = lazy = vec<int>(N << 2);
for (int i = 1; i <= N; i++)
cin >> h[i];
sort(h.begin() + 1, h.end());
build();
while (M--)
{
char q;
cin >> q;
if (q == 'F')
{
int c, H;
cin >> c >> H;
int l1 = query1(H, 0);
int x = query2(l1 + c - 1);
int r1 = query1(x, 0) - 1;
int r2 = query1(x, 1);
int l2 = r2 - (l1 + c - 1 - r1) + 1;
if (l1 <= r1) update(l1, r1);
if (l2 <= r2) update(l2, r2);
}
else
{
int mn, mx;
cin >> mn >> mx;
int l = query1(mn, 0);
int r = query1(mx, 1);
if (l == -1 || r == -1)
cout << "0\n";
else cout << r - l + 1 << '\n';
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |