#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 3e5 + 10;
const int lim = N * 2;
int v[N];
struct seg{
vector <int> st;
int N;
void ass(int n) {
N = n;
st.assign(n * 4 + 10, 0);
}
void upd(int id, int l, int r, int p, int v) {
if (l > p || r < p)
return;
if (l == r) {
st[id] = v;
return;
}
int m = (l + r) / 2;
upd(id * 2, l, m, p, v);
upd(id * 2 + 1, m + 1, r, p, v);
st[id] = max(st[id * 2], st[id * 2 + 1]);
}
int range(int id, int l, int r, int u, int v) {
if (l > v || r < u)
return 0;
if (l >= u && r <= v) {
return st[id];
}
int m = (l + r) / 2;
return max(range(id * 2, l, m, u, v), range(id * 2 + 1, m + 1, r, u, v));
}
int find(int id, int l, int r, int v) {
if (st[id] < v)
return r + 1;
if (l == r)
return l;
int m = (l + r) / 2;
if (st[id * 2] >= v)
return find(id * 2, l, m, v);
return find(id * 2 + 1, m + 1, r, v);
}
void upd(int a, int b) {
upd(1, 1, N, a, b);
}
int find(int v) {
return find(1, 1, N, v);
}
} L, R;
int a, n;
void change(int x, int b) {
v[x] = b;
if (x > a) {
R.upd(x - a + 1, b);
}
if (x < a) {
L.upd(a - x + 1, b);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> a;
int st = n + 1;
L.ass(n);
R.ass(n);
vector <int> pos;
for (int i = 1; i <= n; i++) {
cin >> v[i];
if (n - v[i] < 10)
pos.pb(i);
}
sort(all(pos), [&] (int x, int y) {return v[x] > v[y];});
for (int j = 0; j < sz(pos); j++)
v[pos[j]] = lim - j;
for (int i = 1; i <= n; i++) {
change(i, v[i]);
}
int q;
cin >> q;
for (int i = 1; i <= q; i++) {
char ch;
cin >> ch;
if (ch == 'E') {
int p, e;
cin >> p >> e;
auto it = find(all(pos), p);
if (it != pos.end()) {
pos.erase(it);
}
pos.insert(pos.begin() + e - 1, p);
if (sz(pos) > 10) {
change(pos.back(), st);
st++;
pos.pop_back();
}
for (int j = 0; j < sz(pos); j++) {
change(pos[j], lim - j);
}
} else {
int b;
cin >> b;
if (a == b) {
cout << 0 << '\n';
continue;
}
if (a < b) {
int mx = R.range(1, 1, n, 1, b - a + 1);
cout << min(L.find(mx) - 1, a) + b - a - 1 << '\n';
} else {
int mx = L.range(1, 1, n, 1, a - b + 1);
cout << min(R.find(mx) - 1, n - a + 1) + a - b - 1 << '\n';
}
}
}
//cout << R.find(L.range(1, 1, n, 1, 2)) << '\n';
return 0;
}
/*
5 3
5 1 2 4 3
17
F 1
F 2
F 3
F 4
F 5
E 2 1
F 1
F 2
F 3
F 4
F 5
E 5 2
F 1
F 2
F 3
F 4
F 5
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
3 ms |
600 KB |
Output is correct |
5 |
Correct |
8 ms |
860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
394 ms |
4988 KB |
Output is correct |
2 |
Correct |
326 ms |
5332 KB |
Output is correct |
3 |
Correct |
357 ms |
5204 KB |
Output is correct |
4 |
Correct |
358 ms |
5164 KB |
Output is correct |
5 |
Correct |
404 ms |
5972 KB |
Output is correct |
6 |
Correct |
392 ms |
6360 KB |
Output is correct |
7 |
Correct |
392 ms |
5940 KB |
Output is correct |
8 |
Correct |
406 ms |
6328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
46 ms |
5708 KB |
Output is correct |
2 |
Correct |
43 ms |
5712 KB |
Output is correct |
3 |
Correct |
39 ms |
5580 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
75 ms |
12256 KB |
Output is correct |
6 |
Correct |
72 ms |
12120 KB |
Output is correct |
7 |
Correct |
65 ms |
12116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
860 KB |
Output is correct |
2 |
Correct |
34 ms |
1128 KB |
Output is correct |
3 |
Correct |
60 ms |
3164 KB |
Output is correct |
4 |
Correct |
60 ms |
3268 KB |
Output is correct |
5 |
Correct |
80 ms |
1780 KB |
Output is correct |
6 |
Correct |
113 ms |
4692 KB |
Output is correct |
7 |
Correct |
118 ms |
2828 KB |
Output is correct |
8 |
Correct |
198 ms |
6416 KB |
Output is correct |
9 |
Correct |
446 ms |
17420 KB |
Output is correct |
10 |
Correct |
262 ms |
5152 KB |
Output is correct |
11 |
Correct |
328 ms |
6740 KB |
Output is correct |
12 |
Correct |
410 ms |
14928 KB |
Output is correct |
13 |
Correct |
383 ms |
17500 KB |
Output is correct |