Untitled
domovonok
c_cpp
a year ago
3.0 kB
2
Indexable
Never
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(x...) #endif using ll = long long; using ull = unsigned long long; using db = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<db, db>; using tiii = tuple<int, int, int>; using str = string; #define vt vector #define pb push_back #define eb emplace_back #define ins insert #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)x.size() #define mp make_pair #define mt make_tuple #define fi first #define se second constexpr int maxA = 1e6; struct segtree { int size; vt<int> tree; void init(int n) { size = 1; while (size < n) size *= 2; tree.assign(2 * size - 1, INT_MIN); } void set(int i, int v, int x, int lx, int rx) { if (rx - lx == 1) { tree[x] = v; } else { int m = (lx + rx) / 2; if (i < m) { set(i, v, x * 2 + 1, lx, m); } else { set(i, v, x * 2 + 2, m, rx); } tree[x] = max(tree[x * 2 + 1], tree[x * 2 + 2]); } } void set(int i, int v) { set(i, v, 0, 0, size); } int calc(int l, int r, int v, int x, int lx, int rx) { if (rx - lx == 1) { return tree[x]; } else { int m = (lx + rx) / 2; if (tree[x * 2 + 1] > v && m > l) { int t = calc(l, r, v, x * 2 + 1, lx, m); if (t == INT_MIN && tree[x * 2 + 2] > v) { return calc(l, r, v, x * 2 + 2, m, rx); } return t; } else if (tree[x * 2 + 2] > v) { return calc(l, r, v, x * 2 + 2, m, rx); } return INT_MIN; } } int calc(int l, int v) { return calc(l, size, v, 0, 0, size); } }; void solve() { segtree tr; tr.init(2 * maxA + 1); int n; cin >> n; vt<int> a(n); map<int, set<int>> cnts; for (int i = 0; i < n; i++) { cin >> a[i]; cnts[a[i]].ins(i); tr.set(a[i] + maxA, i); } int q; cin >> q; while (q--) { int t, i; cin >> t >> i; i--; if (t == 1) { int c = tr.calc(a[i] + 1 + maxA, i); cout << a[c] << '\n'; } else { cnts[a[i]].erase(i); cnts[-a[i]].ins(i); tr.set(a[i] + maxA, (cnts[a[i]].empty() ? INT_MIN : *--cnts[a[i]].end())); tr.set(-a[i] + maxA, *--cnts[-a[i]].end()); a[i] = -a[i]; } } } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int tests = 1; // cin >> tests; while (tests--) { solve(); } return 0; }