// source problem :
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define lb lower_bound
#define ub upper_bound
#define MASK(i) (1LL << (i))
void ckmax(int& f, int s)
{
f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
f = (f < s ? f : s);
}
const int inf = 2e9;
int st[1 << 18] = {}, lz[1 << 18] = {}, a[1 << 17], n;
void build(int id = 1, int l = 1, int r = 1 << 17)
{
if (l == r)
{
if (l <= n) st[id] = a[l];
else st[id] = inf;
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
void down(int id)
{
if (!lz[id]) return;
for (int i : {id << 1, id << 1 | 1})
{
st[i] += lz[id];
lz[i] += lz[id];
}
lz[id] = 0;
}
void update(int u, int v, int x, int id = 1, int l = 1, int r = 1 << 17)
{
if (r < u || l > v) return;
if (l >= u && r <= v)
{
st[id] += x;
lz[id] += x;
return;
}
down(id);
int mid = (l + r) >> 1;
update(u, v, x, id << 1, l, mid);
update(u, v, x, id << 1 | 1, mid + 1, r);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
int find_first(int x, int id = 1, int l = 1, int r = 1 << 17)
{
if (l == r) return l;
down(id);
int mid = (l + r) >> 1;
if (st[id << 1] >= x) return find_first(x, id << 1, l, mid);
return find_first(x, id << 1 | 1, mid + 1, r);
}
int get(int pos, int id = 1, int l = 1, int r = 1 << 17)
{
if (l == r) return st[id];
down(id);
int mid = (l + r) >> 1;
if (pos <= mid) return get(pos, id << 1, l, mid);
return get(pos, id << 1 | 1, mid + 1, r);
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
build();
while (q--)
{
char c;
int l, r;
cin >> c >> l >> r;
if (c == 'C') cout << find_first(r + 1) - find_first(l) << '\n';
else
{
int p = find_first(r);
if (n - p + 1 <= l) update(p, n, 1);
else
{
int k = get(p + l - 1);
int pp = find_first(k + 1) - 1;
int ppp = find_first(k) - 1;
update(p, ppp, 1);
l -= ppp - p + 1;
update(pp - l + 1, pp, 1);
}
}
}
return 0;
}
# | 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... |