#include <bits/stdc++.h> using namespace std; const int MXN = 2e5+5; int up[MXN][25]; int t[MXN*4]; vector <int> lazy(4*MXN,-1); int k[MXN]; int p[MXN]; void applay(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)/2; applay(node*2,lazy[node],l,mid); applay(node*2+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) { applay(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(int node, int l, int r, int val) { if (val <= 0) return l; if (val >= t[node]) { if (l == r) return l; } if (l == r) return l; push(node, l, r); int mid = (l + r) >> 1; if (t[node<<1] >= val) return get(node<<1, l, mid, val); return get(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 len = r - l + 1; int lg = 31 - __builtin_clz(len); int a = up[l][lg]; int b = up[r - (1<<lg) + 1][lg]; return merge(a,b); } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { for (int i = 0; i <= N+1; i++) p[i] = 0; for (int i = 0; i < 4*N; i++) { t[i] = 0; lazy[i] = -1; } for (int i = 0; i < N-1; i++) { k[i] = K[i]; up[i][0] = i; } for (int i = 1; i <= 20; i++) { for (int j = 0; j + (1<<i) - 1 < N-1; j++) { up[j][i] = merge(up[j][i-1],up[j+(1<<(i-1))][i-1]); } } for (int i = 1; i <= N; i++) { update(1,1,N,i,i,1); } for (int i = 0; i < C; i++) { int l = get(1,1,N,S[i]+1); int r = get(1,1,N,E[i]+1); int mx =getmax(l-1,r-2); if (mx != -1) mx = k[mx]; if (l < r) update(1,1,N,l+1,r,0); if (mx < R) { p[l]++; p[r+1]--; } } int ans = 1; for (int i = 1; i <= N; i++) { p[i] = p[i-1] + p[i]; if (p[ans] < p[i]) ans = i; } return ans-1; }