题解 CF840D 【Destiny】

比较推荐的一道主席树入门题。 我们思考主席树的本质，其实就是可以刨出一个区间$l,r$让我们可以在树高复杂度$log$的基础上进行一波常规线段树不能进行的、权值查找操作。那么由于主席树本质上是一棵权值线段树，所以直接$return$的$val$一定是最小的（只要我们保证先查找左子树）。 然后…然后就没有然后了qwq ```cpp #include<cstdio> #include<iostream> #include<algorithm> #define il inline #define MAXN 500510 #define mid ((l + r) >> 1) using namespace std ; int a, b, c ; int pos, N, base[MAXN], aft[MAXN], M, i ; int cnt, Len, T[MAXN << 5], L[MAXN << 5], R[MAXN << 5], sum[MAXN << 5] ; il int qr(){ int k = 0, f = 1; char c = getchar() ; while(!isdigit(c)){ if (c == '-') f = -1 ; c = getchar() ; } while(isdigit(c)){ k = (k << 1) + (k << 3) + c - 48 ; c = getchar() ; } return k * f; } il int build(int l, int r){ int rt = ++ cnt ; sum[rt] = 0 ; if(l < r){ L[rt] = build(l, mid) ; R[rt] = build(mid + 1, r) ; } return rt; } il int update(int last, int l, int r, int x){ int rt = ++ cnt ; sum[rt] = sum[last] + 1 ; R[rt] = R[last] ; L[rt] = L[last] ; if (l < r){ if (x <= mid) L[rt] = update(L[last], l, mid, x) ; else R[rt] = update(R[last], mid + 1, r, x) ; } return rt ; } il int query(int Left, int Right, int l, int r, int k){ if (l == r) return aft[l] ; int qwq ; // if (sum[Right] - sum[Left] <= k) return -1 ; int x = sum[L[Right]] - sum[L[Left]], y = sum[R[Right]] - sum[R[Left]] ; if (x > k) if ((qwq = query(L[Left], L[Right], l, mid, k)) > 0) return qwq ; if (y > k) if ((qwq = query(R[Left], R[Right], mid + 1, r, k)) > 0) return qwq ; return -1 ; } int main(){ cin >> N >> M; for(i = 1; i <= N; i ++){ base[i] = qr() ; aft[i] = base[i] ; } sort(aft + 1, aft + N + 1) ; Len = unique(aft + 1, aft + N + 1) - (aft + 1) ; T[0] = build(1, Len) ; for(i = 1; i <= N; i ++){ pos = lower_bound(aft + 1, aft + Len + 1, base[i]) - aft; T[i] = update(T[i - 1], 1, Len, pos) ; } for(i = 1; i <= M; i ++){ scanf("%d%d%d", &a, &b, &c) ; int k = (b - a + 1) / c ; cout << query(T[a - 1], T[b], 1, Len, k) << endl ; } return 0 ; } ```