划分树虽然可以做，但是代码不好记。
看某人blog学习了主席树的简单操作。
引用某大牛的话来解释一下主席树：
所谓主席树呢，就是对原来的数列[1..n]的每一个前缀[1..i]（1≤i≤n）建立一棵线段树，线段树的每一个节点存某个前缀[1..i]中属于区间[L..R]的数一共有多少个（比如根节点是[1..n]，一共i个数，sum[root] = i；根节点的左儿子是[1..(L+R)/2]，若不大于(L+R)/2的数有x个，那么sum[root.left] = x）。若要查找[i..j]中第k大数时，设某结点x，那么x.sum[j] - x.sum[i - 1]就是[i..j]中在结点x内的数字总数。而对每一个前缀都建一棵树，会MLE，观察到每个[1..i]和[1..i-1]只有一条路是不一样的，那么其他的结点只要用回前一棵树的结点即可，时空复杂度为O(nlogn)。
——具体看代码（有详细注释）
1 #include <cstdio> 2 #include <algorithm> 3 #define lc son[now][0], l, mid 4 #define rc son[now][1], mid + 1, r 5 6 using namespace std; 7 8 const int N = 100000 + 5; 9 10 int T, n, q, tot; 11 int a[N], b[N], son[20 * N][2], sum[20 * N], rt[20 * N]; 12 //主席树第 i 棵树存的是 a[0] - a[i] 的树（前缀和） 13 //主席树一个节点 sum 存的是当前线段所包含的数的个数。。晕。 14 //rt 是每一棵树的根节点编号 15 //a 保存原数组，b 保存排序后的数组 16 17 //注意 & 的使用 18 inline void build(int &now, int l, int r) 19 { 20 now = ++tot; 21 sum[now] = 0; 22 if(l == r) return; 23 int mid = (l + r) >> 1; 24 build(lc); 25 build(rc); 26 } 27 28 inline void update(int &now, int l, int r, int last, int x) 29 { 30 now = ++tot; 31 //继承上个节点的孩子 32 son[now][0] = son[last][0]; 33 son[now][1] = son[last][1]; 34 //继承上一个节点的 sum 并加上当前所加入的数的个数（就是1） 35 sum[now] = sum[last] + 1; 36 if(l == r) return; 37 int mid = (l + r) >> 1; 38 if(x <= mid) update(lc, son[now][0], x); 39 else update(rc, son[now][1], x); 40 } 41 42 //因为每个节点存的是有多少个数在当前区间 43 //求区间 [1,3] 即求 rt[3] - rt[0] 内的数 44 //可通过递归二分解决 45 inline int query(int s, int t, int l, int r, int x) 46 { 47 if(l == r) return l; 48 int mid = (l + r) >> 1, cnt = sum[son[t][0]] - sum[son[s][0]]; 49 if(x <= cnt) return query(son[s][0], son[t][0], l, mid, x); 50 else return query(son[s][1], son[t][1], mid + 1, r, x - cnt); 51 } 52 53 int main() 54 { 55 int i, x, y, z, sz; 56 scanf("%d", &T); 57 while(T--) 58 { 59 scanf("%d %d", &n, &q); 60 for(i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i]; 61 sort(b + 1, b + n + 1); 62 sz = unique(b + 1, b + n + 1) - (b + 1);//求不同的数一共有几个，即区间大小 63 tot = 0; 64 build(rt[0], 1, sz); 65 //用每个元素在 b 中的坐标重置 a 数组（离散化） 66 for(i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + sz + 1, a[i]) - b; 67 for(i = 1; i <= n; i++) update(rt[i], 1, sz, rt[i - 1], a[i]); 68 while(q--) 69 { 70 scanf("%d %d %d", &x, &y, &z); 71 printf("%d ", b[query(rt[x - 1], rt[y], 1, sz, z)]); 72 } 73 } 74 return 0; 75 }
——代码
1 #include <cstdio> 2 #include <algorithm> 3 #define debug puts("***********"); 4 5 const int MAXN = 100001; 6 int n, m, cnt; 7 int b[MAXN], root[MAXN]; 8 struct node 9 { 10 int a, rank; 11 }p[MAXN]; 12 struct pst 13 { 14 int sum, ls, rs; 15 }t[MAXN * 20]; 16 17 inline bool cmp(node x, node y) 18 { 19 return x.a < y.a; 20 } 21 22 inline void insert(int x, int &now, int l, int r) 23 { 24 t[++cnt] = t[now]; 25 now = cnt; 26 t[now].sum++; 27 if(l == r) return; 28 int mid = (l + r) >> 1; 29 if(x <= mid) insert(x, t[now].ls, l, mid); 30 else insert(x, t[now].rs, mid + 1, r); 31 } 32 33 inline int query(int x, int y, int k, int l, int r) 34 { 35 if(l == r) return l; 36 int ans = t[t[y].ls].sum - t[t[x].ls].sum, mid = (l + r) >> 1;; 37 if(k <= ans) return query(t[x].ls, t[y].ls, k, l, mid); 38 else return query(t[x].rs, t[y].rs, k - ans, mid + 1, r); 39 } 40 41 int main() 42 { 43 int i, x, y, z; 44 scanf("%d %d", &n, &m); 45 46 //没有重复元素的离散化 47 for(i = 1; i <= n; i++) scanf("%d", &p[i].a), p[i].rank = i; 48 std::sort(p + 1, p + n + 1, cmp); 49 for(i = 1; i <= n; i++) b[p[i].rank] = i; 50 51 for(i = 1; i <= n; i++) 52 { 53 root[i] = root[i - 1]; 54 insert(b[i], root[i], 1, n); 55 } 56 for(i = 1; i <= m; i++) 57 { 58 scanf("%d %d %d", &x, &y, &z); 59 printf("%d ", p[query(root[x - 1], root[y], z, 1, n)].a); 60 } 61 return 0; 62 }