#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using ll = long long;
using pii = pair<int, int>;
#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
assert(l <= r);
return uniform_int_distribution<ll> (l, r)(rng);
}
const int N = 250003;
int n, q, d[N], pos[N];
vector<pii> val;
int a;
namespace ST{
int st[N << 2];
void _update(int id, int l, int r, int pos, int val){
if(l == r){
st[id] = val;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid)
_update(id << 1, l, mid, pos, val);
else
_update(id << 1 | 1, mid + 1, r, pos, val);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
int _get(int id, int l, int r, int tl, int tr){
if(l > tr or tl > r)
return 0;
if(tl <= l and r <= tr)
return st[id];
int mid = (l + r) >> 1;
return max(_get(id << 1, l, mid, tl, tr), _get(id << 1 | 1, mid + 1, r, tl, tr));
}
int _walkl(int id, int l, int r, int tl, int tr, int val){
if(l > tr or tl > r)
return -1;
if(st[id] < val)
return -1;
if(l == r)
return l;
int mid = (l + r) >> 1;
int res = _walkl(id << 1, l, mid, tl, tr, val);
if(res != -1)
return res;
return _walkl(id << 1 | 1, mid + 1, r, tl, tr, val);
}
int _walkr(int id, int l, int r, int tl, int tr, int val){
if(l > tr or tl > r)
return -1;
if(st[id] < val)
return -1;
if(l == r)
return l;
int mid = (l + r) >> 1;
int res = _walkr(id << 1 | 1, mid + 1, r, tl, tr, val);
if(res != -1)
return res;
return _walkr(id << 1, l, mid, tl, tr, val);
}
void update(int pos, int val){ _update(1, 1, n, pos, val); }
int get(int l, int r){ return _get(1, 1, n, l, r); }
int walkl(int l, int r, int val){ return _walkl(1, 1, n, l, r, val); }
int walkr(int l, int r, int val){ return _walkr(1, 1, n, l, r, val); }
}
void solve(){
cin >> n >> a;
for(int i = 1; i <= n; ++i){
cin >> d[i];
pos[d[i]] = i;
}
for(int i = 1; i <= n; ++i){
val.emplace_back(i, pos[i]);
ST::update(i, d[i]);
}
cin >> q;
while(q--){
char c;
cin >> c;
if(c == 'E'){
int i, e;
cin >> i >> e;
set<int> saved;
vector<pii> nx;
while(sz(nx) + 1 < e){
if(!saved.count(val.back().S)){
nx.push_back(val.back());
saved.insert(val.back().S);
}
val.pop_back();
}
ST::update(i, val.back().F + 1);
val.emplace_back(val.back().F + 1, i);
reverse(all(nx));
while(!nx.empty()){
ST::update(nx.back().S, val.back().F + 1);
val.emplace_back(val.back().F + 1, nx.back().S);
nx.pop_back();
}
}
else{
int b;
cin >> b;
if(b == a){
cout << 0 << '\n';
continue;
}
if(a == 1 or a == n){
cout << abs(a - b) << '\n';
continue;
}
if(b < a){
int mx = ST::get(b, a - 1);
int rv = ST::walkl(a + 1, n, mx);
if(rv == -1)
rv = n + 1;
cout << rv - b - 1 << '\n';
}
else{
int mx = ST::get(a + 1, b);
int lv = ST::walkr(1, a - 1, mx);
if(lv == -1)
lv = 0;
cout << b - lv - 1 << '\n';
}
}
}
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(0);
#define task "troll"
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int test = 1;
// cin >> test;
for(int i = 1; i <= test; ++i){
// cout << "Case #" << i << ": ";
solve();
}
#ifdef LOCAL
cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
#endif
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
cake.cpp: In function 'int32_t main()':
cake.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
157 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
158 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |