#include <bits/stdc++.h> using namespace std; const int MXN = 200005; int tree[MXN * 4]; void build(int node, int l, int r) { if (l == r) { tree[node] = 1; return; } int mid = (l + r) >> 1; build(node << 1, l, mid); build(node << 1 | 1, mid + 1, r); tree[node] = tree[node << 1] + tree[node << 1 | 1]; } void update(int node, int l, int r, int pos) { if (l == r) { tree[node] = 0; return; } int mid = (l + r) >> 1; if (pos <= mid) update(node << 1, l, mid, pos); else update(node << 1 | 1, mid + 1, r, pos); tree[node] = tree[node << 1] + tree[node << 1 | 1]; } int get(int node, int l, int r, int k) { if (l == r) return l; int mid = (l + r) >> 1; if (tree[node << 1] >= k) return get(node << 1, l, mid, k); return get(node << 1 | 1, mid + 1, r, k - tree[node << 1]); } int GetBestPosition(int n, int c, int R, int *K, int *S, int *E) { vector<int> pref(n + 1, 0); for (int i = 0; i < n - 1; i++) { pref[i + 1] = pref[i] + (K[i] > R); } build(1, 1, n); vector<int> jump(n + 2); for (int i = 1; i <= n; i++) jump[i] = i + 1; vector<int> d(n + 2, 0); for (int i = 0; i < c; i++) { int needL = S[i] + 1; int l = (tree[1] < needL ? n : get(1, 1, n, needL)); int needR = E[i] + 2; int r = (tree[1] < needR ? n : get(1, 1, n, needR)); for (int j = jump[l]; j < r; ) { update(1, 1, n, j); int nxt = jump[j]; j = nxt; } jump[l] = r; if (r - 1 >= l) { if (pref[r - 1] - pref[l - 1] == 0) { d[l]++; d[r + 1]--; } } } int mx = -1, best = 0, cur = 0; for (int i = 1; i <= n; i++) { cur += d[i]; if (cur > mx) { mx = cur; best = i - 1; } } return best; }