#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define printv(a, b) {\
for(auto pv : a) b << pv << " ";\
b << "\n";\
}
#define int int_fast32_t
using namespace std;
using pii = pair<int, int>;
ostream& operator<<(ostream& o, pii p){
return o << '(' << p.F << ',' << p.S << ')';
}
bool assertflag = false;
void waassert(bool t){
if(!assertflag || t) return;
cout << "OAO\n";
exit(0);
}
struct Node{
int mn = 0, mx = 0, tag = -1, d = -1, sz;
int rmn(){
if(tag == -1) return mn;
return min(tag, tag + d * (sz - 1));
}
int rmx(){
if(tag == -1) return mx;
return max(tag, tag + d * (sz - 1));
}
};
struct SegmentTree{
vector<Node> st;
int ts = 0;
int lr, rr;
void init(int n, int _lr, int _rr){
st.resize(4 * n);
lr = _lr;
rr = _rr;
}
void push(int id){
if(st[id].tag == -1) return;
int lc = 2 * id + 1, rc = 2 * id + 2;
st[lc].tag = st[id].tag;
st[rc].tag = st[id].tag + st[id].d * st[lc].sz;
st[lc].d = st[rc].d = st[id].d;
st[id].mn = st[id].rmn();
st[id].mx = st[id].rmx();
st[id].tag = st[id].d = -1;
}
void build(int l = -1, int r = -1, int id = 0){
if(l == -1) l = lr;
if(r == -1) r = rr;
st[id].sz = r - l + 1;
if(l == r) return;
int m = (l + r) / 2;
build(l, m, 2 * id + 1);
build(m + 1, r, 2 * id + 2);
}
void modify(int l, int r, int f, int d = 0, int L = -1, int R = -1, int id = 0){
if(L == -1) L = lr;
if(R == -1) R = rr;
//cerr << "modify " << l << " " << r << " " << f << " " << d << " " << L << " " << R << "\n";
//waassert(L <= l && r <= R && l <= r);
if(l == L && r == R){
st[id].tag = f;
st[id].d = d;
return;
}
push(id);
int M = (L + R) / 2;
if(r <= M) modify(l, r, f, d, L, M, 2 * id + 1);
else if(l > M) modify(l, r, f, d, M + 1, R, 2 * id + 2);
else{
modify(l, M, f, d, L, M, 2 * id + 1);
modify(M + 1, r, f + d * (M + 1 - l), d, M + 1, R, 2 * id + 2);
}
st[id].mn = min(st[2 * id + 1].rmn(), st[2 * id + 2].rmn());
st[id].mx = max(st[2 * id + 1].rmx(), st[2 * id + 2].rmx());
}
int querymn(int l, int r, int L = -1, int R = -1, int id = 0){
if(L == -1) L = lr;
if(R == -1) R = rr;
//waassert(L <= l && r <= R && l <= r);
if(l == L && r == R) return st[id].rmn();
push(id);
int M = (L + R) / 2;
if(r <= M) return querymn(l, r, L, M, 2 * id + 1);
else if(l > M) return querymn(l, r, M + 1, R, 2 * id + 2);
else{
return min(querymn(l, M, L, M, 2 * id + 1), querymn(M + 1, r, M + 1, R, 2 * id + 2));
}
}
int querymx(int l, int r, int L = -1, int R = -1, int id = 0){
if(L == -1) L = lr;
if(R == -1) R = rr;
//waassert(L <= l && r <= R && l <= r);
if(l == L && r == R) return st[id].rmx();
push(id);
int M = (L + R) / 2;
if(r <= M) return querymx(l, r, L, M, 2 * id + 1);
else if(l > M) return querymx(l, r, M + 1, R, 2 * id + 2);
else{
return max(querymx(l, M, L, M, 2 * id + 1), querymx(M + 1, r, M + 1, R, 2 * id + 2));
}
}
};
int n, a;
void assertrange(int l, int r){
waassert(l <= r && 1 <= l && r <= n);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> a;
SegmentTree pos, order;
pos.init(n, 1, n);
order.init(n, 1, n);
pos.build();
order.build();
vector<int> d(n + 1);
map<int, int, greater<>> rk;
for(int i = 1; i <= n; i++){
cin >> d[i];
rk[d[i]] = i;
}
int l = a, r = a;
pos.modify(a, a, 1);
order.modify(1, 1, a);
for(int i = 2; i <= n; i++){
if(r == n){
l--;
pos.modify(l, l, i);
order.modify(i, i, l);
}
else if(l == 1){
r++;
pos.modify(r, r, i);
order.modify(i, i, r);
}
else if(d[l - 1] < d[r + 1]){
l--;
pos.modify(l, l, i);
order.modify(i, i, l);
}
else{
r++;
pos.modify(r, r, i);
order.modify(i, i, r);
}
}
int q;
cin >> q;
while(q--){
char c;
cin >> c;
if(c == 'F'){
int b;
cin >> b;
cout << pos.querymn(b, b) - 1 << "\n";
continue;
}
int i, e;
cin >> i >> e;
vector<int> tmp;
for(int j = 0; j < e - 1; j++){
tmp.eb(rk.begin()->S);
rk.erase(rk.begin());
}
tmp.eb(i);
rk.erase(d[i]);
while(!tmp.empty()){
d[tmp.back()] = rk.empty() ? 1 : rk.begin()->F + 1;
rk[d[tmp.back()]] = tmp.back();
tmp.pop_back();
}
int now = i;
int nowpos = pos.querymn(now, now);
if(nowpos == 1) continue;
int l = order.querymn(1, nowpos - 1), r = order.querymx(1, nowpos - 1);
while(true){
//cerr << "test " << l << " " << r << " " << now << "\n";
if(now == l - 1){
int go = n + 1;
for(auto it = rk.begin(); it->S != now; it++){
if(it->S > r) go = min(go, it->S);
}
if(go - 1 > r){
pos.modify(r + 1, go - 1, nowpos, 1);
order.modify(nowpos, nowpos + (go - 1) - (r + 1), r + 1, 1);
nowpos += go - 1 - r;
}
pos.modify(now, now, nowpos);
order.modify(nowpos, nowpos, now);
nowpos++;
r = go - 1;
l = now;
if(go != n + 1) now = go;
else if(now == 1) break;
else{
pos.modify(1, now - 1, nowpos + now - 2, -1);
order.modify(nowpos, n, now - 1, -1);
break;
}
}
else{
int go = 0;
for(auto it = rk.begin(); it->S != now; it++){
if(it->S < l) go = max(go, it->S);
}
if(go + 1 < l){
pos.modify(go + 1, l - 1, nowpos + (l - 1) - (go + 1), -1);
order.modify(nowpos, nowpos + (l - 1) - (go + 1), l - 1, -1);
nowpos += l - 1 - go;
}
pos.modify(now, now, nowpos);
order.modify(nowpos, nowpos, now);
nowpos++;
l = go + 1;
r = now;
if(go != 0) now = go;
else if(now == n) break;
else{
pos.modify(now + 1, n, nowpos, 1);
order.modify(nowpos, n, now + 1, 1);
break;
}
}
}
}
return 0;
}
Compilation message
cake.cpp:11:13: error: '::main' must return 'int'
11 | #define int int_fast32_t
| ^~~~~~~~~~~~
cake.cpp:126:1: note: in expansion of macro 'int'
126 | int main(){
| ^~~
