题目链接：点击打开链接
题意：
给定n长的序列，q个询问
下面n个数字给出序列
每个询问[l, r] k ，输出该区间中第k大的数
先建一个n个节点的空树，，然后每次从后往前新建一棵树，依附原来的空树建。询问就是在树上二分。
#include <stdio.h>#include <stdlib.h>#include <algorithm>#include <vector>#include <iostream>#include <cstring>using namespace std;const int N = 100010;const int M = N * 30;int n, q, tot;int a[N];int T[M], lson[M], rson[M], c[M];vector<int>G;void input(){G.clear();for (int i = 1; i <= n; i++)scanf("%d", &a[i]), G.push_back(a[i]);sort(G.begin(), G.end());G.erase(unique(G.begin(), G.end()), G.end());for (int i = 1; i <= n; i++)a[i] = lower_bound(G.begin(), G.end(), a[i]) – G.begin() + 1;}int build(int l, int r){int root = tot++;c[root] = 0;if (l != r){int mid = (l + r) >> 1;lson[root] = build(l, mid);rson[root] = build(mid + 1, r);}return root;}int updata(int root, int pos, int val){int newroot = tot++, tmp = newroot;c[newroot] = c[root] + val;int l = 1, r = G.size();while (l <= r){int mid = (l + r) >> 1;if (pos <= mid){lson[newroot] = tot++; rson[newroot] = rson[root];newroot = lson[newroot]; root = lson[root];r = mid – 1;}else {rson[newroot] = tot++; lson[newroot] = lson[root];newroot = rson[newroot]; root = rson[root];l = mid + 1;}c[newroot] = c[root] + val;}return tmp;}int query(int L, int R, int k){int l = 1, r = G.size(), ans = l;while (l <= r){int mid = (l + r) >> 1;if (c[lson[L]] – c[lson[R]] >= k){ans = mid;r = mid – 1;L = lson[L];R = lson[R];}else {l = mid + 1;k -= c[lson[L]] – c[lson[R]];L = rson[L];R = rson[R];}}return ans;}int main(){while (~scanf("%d%d", &n, &q)){input();tot = 0;T[n + 1] = build(1, G.size());for (int i = n; i; i–)T[i] = updata(T[i + 1], a[i], 1);while (q–){int l, r, k; scanf("%d %d %d", &l, &r, &k);printf("%d\n", G[query(T[l], T[r+1], k)- 1]);}}return 0;}
路遥知马力，日久见人心。
