1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <string> 5 #include <cmath> 6 #include <iostream> 7 #include <stack> 8 using namespace std; 9 #define N 10001010 11 /*12 主席树13 http://www.bilibili.com/video/av4619406/14 http://www.cnblogs.com/Empress/p/4652449.html15 题意:在一堆数里面有m个询问,每个询问求区间[l,r]里面的第k小的数是哪个.16 要认识权值线段树：在以节点i为根的树中,[1,i]区间内包含的数的个数.17 */18 struct node19 {20     int l, r, sum;//sum储存的就是权值21 }tree[N*40];22 int root[N];//储存根节点23 int a[N], b[N], tot;24 25 void update(int pre, int &now, int x, int l, int r)26 {27     tree[++tot] = tree[pre];//把上一个版本的线段树给现在的版本,然后对要修改的那条链进行更新28     now = tot;29     tree[now].sum++;//因为插入了新的数,所以要更新+130     if(l == r) return ;31     int m = (l + r) >> 1;32     if(x <= m) update(tree[pre].l, tree[now].l, x, l, m);33     else update(tree[pre].r, tree[now].r, x, m + 1, r);34 }35 36 int query(int left, int right, int k, int l, int r)37 {38     if(l == r) return l;39     int m = (l + r) >> 1;40     int sum = tree[tree[right].l].sum - tree[tree[left].l].sum;//如果左子树已经有k个数,那么答案就在左边41     if(k <= sum) return query(tree[left].l, tree[right].l, k, l, m);42     else return query(tree[left].r, tree[right].r, k - sum, m + 1, r);43 }44 45 int main()46 {47 //    int t;48 //    scanf("%d", &t);49 //    while(t--) {50         int n, m;51         scanf("%d%d", &n, &m);52         tot = 0;53         for(int i = 1; i <= n; i++) {54             scanf("%d", &a[i]);55             b[i] = a[i];56         }57         sort(b + 1, b + 1 + n);58         int cnt = unique(b + 1, b + 1 + n) - b - 1;59         for(int i = 1; i <= n; i++) {60             a[i] = lower_bound(b + 1, b + 1 + cnt, a[i]) - b; //二分找到a[i]的位置61 //            printf("QQQQQ\n");62             update(root[i-1], root[i], a[i], 1, cnt); //root[i-1]表示上一个版本的线段树63         }64         for(int i = 1; i <= m; i++) {65             int l, r, k;66             scanf("%d%d%d", &l, &r, &k);67             int ans = query(root[l-1], root[r], k, 1, cnt); //ans是第k个数的位置68             printf("%d\n", b[ans]); //因为询问的是哪个数,所以要b[ans]69         }70 //    }71     return 0;72 }