求区间第k小的数

    1. #include <bits/stdc++.h>
    2. #define int long long
    3. using namespace std;
    5. const int N = 2e5+5;
    6. int n, q, m, id;
    7. //rt[u]表示存储节点u所在线段树的根节点编号 
    8. int a[N], b[N], root[N];
    9. //L[u]，R[u]分别表示节点u的左/右儿子编号
    10. //s[u]表示节点u的权值(该节点代表的区间中有多少个数) 
    11. int s[N<<5], L[N<<5], R[N<<5];
    13. int build(int l, int r) {
    14.     int rt = ++id;
    15.     s[rt] = 0;
    16.     int mid = l+r>>1;
    17.     if (l < r) {
    18.         L[rt] = build(l, mid);
    19.         R[rt] = build(mid+1, r);
    20.     }
    21.     return rt;
    22. }
    24. int update(int pre, int l, int r, int x) {
    25.     int rt = ++id;
    26.     int mid = l+r>>1; 
    27.     L[rt] = L[pre], R[rt] = R[pre];
    28.     s[rt] = s[pre]+1;
    29.     if (l != r) {
    30.         if (x <= mid) {
    31.             L[rt] = update(L[pre], l, mid, x);
    32.         } else {
    33.             R[rt] = update(R[pre], mid+1, r, x);
    34.         }
    35.     }
    36.     return rt;
    37. }
    39. int query(int u, int v, int l, int r, int k) {
    40.     if (l == r) {
    41.         return l;
    42.     }
    43.     //求出区间[l,r]中的数有多少个 
    44.     int x = s[L[v]]-s[L[u]];
    45.     int mid = l+r>>1;
    46.     //二分查找 
    47.     if (x >= k) {
    48.         return query(L[u], L[v], l, mid, k);
    49.     } else {
    50.         return query(R[u], R[v], mid+1, r, k-x);
    51.     }
    52. }
    54. signed main() {
    55.     ios::sync_with_stdio(false);
    56.     cin.tie(0);
    57.     cin >> n >> q;
    58.     for (int i = 1; i <= n; i++) {
    59.         cin >> a[i];
    60.         b[i] = a[i];
    61.     }
    62.     sort(b+1, b+n+1);
    63.     //离散化
    64.     m = unique(b+1, b+n+1)-b-1;
    65.     //建立一颗有m个节点的空树 
    66.     root[0] = build(1, m);
    67.     for (int i = 1; i <= n; i++) {
    68.         //找到离散化之后的数组中a[i]第一次出现的位置p 
    69.         int p = lower_bound(b+1, b+m+1, a[i])-b;
    70.         /*
    71.           复制上一颗线段树的根节点新建一颗线段树且权值加1，
    72.           对于一个儿子的值域区间，如果权值有变化，
    73.           那么新建一个节点，否则，连到原来的那个节点上
    74.         */ 
    75.         root[i] = update(root[i-1], 1, m, p);
    76.     }
    77.     while (q--) {
    78.         int x, y, z;
    79.         cin >> x >> y >> z;
    80.         //前缀和思想 
    81.         int p = query(root[x-1], root[y], 1, m, z);
    82.         cout << b[p] << "\n";
    83.     }
    84.     return 0;
    85. }