#include <bits/stdc++.h> using namespace std; const int MXN = 2e5+5; int up[MXN][20]; int t[MXN*4]; int lazy[MXN*4]; int k[MXN]; int p[MXN]; void apply(int node, int val, int l, int r) { t[node] = val * (r - l + 1); lazy[node] = val; } void push(int node, int l, int r) { if (lazy[node] != -1) { int mid = (l + r) >> 1; apply(node << 1, lazy[node], l, mid); apply(node << 1 | 1, lazy[node], mid + 1, r); lazy[node] = -1; } } void update(int node, int l, int r, int L, int R, int val) { if (l > R || r < L) return; if (l >= L && r <= R) { apply(node, val, l, r); return; } push(node, l, r); int mid = (l + r) >> 1; update(node << 1, l, mid, L, R, val); update(node << 1 | 1, mid + 1, r, L, R, val); t[node] = t[node << 1] + t[node << 1 | 1]; } int get_pos(int node, int l, int r, int val) { if (l == r) return l; push(node, l, r); int mid = (l + r) >> 1; if (t[node << 1] >= val) return get_pos(node << 1, l, mid, val); return get_pos(node << 1 | 1, mid + 1, r, val - t[node << 1]); } int merge(int x, int y) { if (k[x] > k[y]) return x; return y; } int getmax(int l, int r) { if (l > r) return -1; int lg = 31 - __builtin_clz(r - l + 1); return merge(up[l][lg], up[r - (1 << lg) + 1][lg]); } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { for (int i = 0; i <= N + 2; i++) { p[i] = 0; if (i < 4 * MXN) { t[i] = 0; lazy[i] = -1; } } for (int i = 0; i < N - 1; i++) { k[i] = K[i]; up[i][0] = i; } for (int j = 1; j < 20; j++) { for (int i = 0; i + (1 << j) <= N - 1; i++) { up[i][j] = merge(up[i][j - 1], up[i + (1 << (j - 1))][j - 1]); } } for (int i = 1; i <= N; i++) { update(1, 1, N, i, i, 1); } for (int i = 0; i < C; i++) { int l_orig = get_pos(1, 1, N, S[i] + 1); int r_orig = get_pos(1, 1, N, E[i] + 1); int mx_enemy = -1; if (l_orig < r_orig) { int best_idx = getmax(l_orig - 1, r_orig - 2); if (best_idx != -1) mx_enemy = k[best_idx]; } if (R > mx_enemy) { p[l_orig]++; p[r_orig + 1]--; } if (l_orig < r_orig) { update(1, 1, N, l_orig + 1, r_orig, 0); } } int max_wins = -1, best_pos = 1, cur_wins = 0; for (int i = 1; i <= N; i++) { cur_wins += p[i]; if (cur_wins > max_wins) { max_wins = cur_wins; best_pos = i; } } return best_pos - 1; }