关于主席树：
主席树(Chairman Tree)是一种离线数据结构，使用函数式线段树维护每一时刻离散之后的数字出现的次数，由于各历史版本的线段树结构一致，可以相减得出区间信息，即该区间内出现的数字和对应的数量，由于在线段树内，左子树代表的数字都小与右子树，便可像平衡树一样进行K大询问。新建一颗树是(O(logn))，查询一次也为(O(logn))。
比划分树好想&写多了，但是在POJ上比划分树慢一些。
CODE:
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 const int maxn = 100000 + 100; 5 6 int id[maxn], root[maxn], a[maxn], b[maxn], n, m, size; 7 struct chairman_tree_node { 8 int ls, rs, w; 9 } T[maxn * 23]; 10 void insert(int l, int r, int &pos, int val) { 11 T[++size] = T[pos], pos = size; 12 ++T[pos].w; 13 if(l == r) return ; 14 int mid = (l + r) >> 1; 15 if(val <= mid) insert(l, mid, T[pos].ls, val); 16 else insert(mid + 1, r, T[pos].rs, val); 17 } 18 int query(int p, int q, int l, int r, int k) { 19 if(l == r) return l; 20 int t = T[T[q].ls].w - T[T[p].ls].w; 21 int mid = (l + r) >> 1; 22 if(k <= t) return query(T[p].ls, T[q].ls, l, mid, k); 23 else return query(T[p].rs, T[q].rs, mid + 1, r, k - t); 24 } 25 bool cmp(int x, int y) { 26 return a[x] < a[y]; 27 } 28 int main() { 29 scanf("%d%d", &n, &m); 30 for(int i = 1; i <= n; ++i) { 31 scanf("%d", &a[i]); 32 id[i] = i; 33 } 34 sort(id + 1, id + n + 1, cmp); 35 for(int i = 1; i <= n; ++i) { 36 b[id[i]] = i; 37 } 38 for(int i = 1; i <= n; ++i) { 39 root[i] = root[i - 1]; 40 insert(1, n, root[i], b[i]); 41 } 42 for(int i = 1; i <= m; ++i) { 43 int l, r, k; 44 scanf("%d%d%d", &l, &r, &k); 45 printf("%d ", a[id[query(root[l - 1], root[r], 1, n, k)]]); 46 } 47 return 0; 48 }