题目链接： https://www.luogu.org/problem/P3834
首先要离散化，然后主席树模板。
1 #include2 #include 3 #include 4 #define mid (l+r)/2 5 using namespace std; 6 7 const int N = 200010; 8 int n, q, m, cnt = 0; 9 int a[N], b[N], T[N]; 10 int sum[N<<5], L[N<<5], R[N<<5]; 11 12 inline int build(int l, int r) 13 { 14 int rt = ++ cnt; 15 sum[rt] = 0; 16 if (l < r){ 17 L[rt] = build(l, mid); 18 R[rt] = build(mid+1, r); 19 } 20 return rt; 21 } 22 23 inline int update(int pre, int l, int r, int x) 24 { 25 int rt = ++ cnt; 26 L[rt] = L[pre]; R[rt] = R[pre]; sum[rt] = sum[pre]+1; 27 if (l < r){ 28 if (x update(L[pre], l, mid, x); 29 else R[rt] = update(R[pre], mid+1, r, x); 30 } 31 return rt; 32 } 33 34 inline int query(int u, int v, int l, int r, int k) 35 { 36 if (l >= r) return l; 37 int x = sum[L[v]] - sum[L[u]]; 38 if (x >= k) return query(L[u], L[v], l, mid, k); 39 else return query(R[u], R[v], mid+1, r, k-x); 40 } 41 42 int main() 43 { 44 scanf("%d%d", &n, &q); 45 for (int i = 1; i ){ 46 scanf("%d", &a[i]); 47 b[i] = a[i]; 48 } 49 sort(b+1, b+1+n); 50 m = unique(b+1, b+1+n)-b-1; 51 T[0] = build(1, m); 52 for (int i = 1; i ){ 53 int t = lower_bound(b+1, b+1+m, a[i])-b; 54 T[i] = update(T[i-1], 1, m, t); 55 } 56 while (q --){ 57 int x, y, z; 58 scanf("%d%d%d", &x, &y, &z); 59 int t = query(T[x-1], T[y], 1, m, z); 60 printf("%d\n", b[t]); 61 } 62 return 0; 63 }
Original: https://www.cnblogs.com/zxz666/p/11404113.html
Author: GUET_uzi
Title: 主席树（区间第k小的数）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584191/
转载文章受原作者版权保护。转载请注明原作者出处！