Kth Number
多次询问一个静态区间里的第k大数。怎么搞？
暴力？（还是别想了）
多次构建树状数组？（和暴力有啥区别）
于是一个叫做划分树的东西就登场了。（据说还有个叫归并树的，速度慢一点，就不学了）
划分树详解
——代码
1 #include <cstdio> 2 #include <algorithm> 3 #define N 100001 4 5 using namespace std; 6 7 int n, m; 8 int c[N];//排序后数组 9 int num[20][N], val[20][N]; 10 //一共有20层，每一层元素排放，0层是原数组 11 //num[i] 表示 i 前面有多少个孩子进入左孩子 12 13 inline void build(int l, int r, int k) 14 30 else val[k + 1][rc++] = val[k][i];//到右孩子 31 } 32 build(l, mid, k + 1); 33 build(mid + 1, r, k + 1); 34 } 35 36 inline int query(int l, int r, int k, int ql, int qr, int qk) 37 50 } 51 52 int main() 53 65 } 66 return 0; 67 }View Code
当然还有其他方法，不过代码量都比较大。
可以看看这篇blog
上一篇：【转】二分图的一大坨定理
下一篇：[HNOI2004]宠物收养场（Treap）
模板 划分树
