Untitled
domovonok
c_cpp
a year ago
2.5 kB
5
Indexable
Never
#include <bits/stdc++.h> using namespace std; //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /* ifstream fin("input.txt"); ofstream fout("output.txt"); #define cin fin #define cout fout */ //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// #define fi first #define se second #define eb emplace_back #define ef emplace_front #define lwb lower_bound #define upb upper_bound #define all(x) (x).begin(), (x).end() #define int long long //#define double long double #define ll long long #define X real() #define Y imag() const int INF = 1e18, N = 1000000, P = 998244353, K = 26, C = 300; const double EPS = 1e-7; mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void solve() { int n; cin >> n; vector<int> a(n); for (auto& it : a) cin >> it; vector<vector<pair<int, int>>> d(n / C + 1); for (int i = 0; i < n; i++) { d[i / C].eb(a[i], i); } for (auto& it : d) sort(all(it)); int q; cin >> q; while (q--) { int type, i; cin >> type >> i; i--; if (type == 1) { int val = a[i], ans = a[n - 1]; int j = i / C; for (auto [x, y] : d[j]) { if (x > val && x < ans && y > i) ans = x; } j++; while (j <= n / C) { auto t = upb(all(d[j]), make_pair(val, INF)); if (t != d[j].end()) ans = min(ans, t->fi); j++; } cout << ans << '\n'; } else { int j = i / C; a[i] = -a[i]; for (auto& [x, y] : d[j]) { if (y == i) { x = -x; break; } } sort(all(d[j])); } } } //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// signed main() { //cout << fixed << setprecision(15); ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; //cin >> T; while (T--) { solve(); } }