hdu 2665 Kth number (静态区间第k大，可持久化线段树模板题)
题意：
求区间第k大数
思路：
可持久化线段树。
其实这东西在国内更常见的名字应该是 zhu xi 树？应该是由于“中国高端数据结构领导者”的hjt比较早得引入（？推广？）而得来的。
不过之前没写什么东西都被封，写个zhu xi 树，怕是政治敏感够枪毙100回了orz
似乎也叫函数式线段树。
写个模板题练下手。学习笔记之后补。
/* ***********************************************
Author :111qqz
Created Time :2017年10月16日 星期一 21时51分55秒
File Name :2104.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7int a[N],H[N];
8int cnt;
9int Hash( int x){ return lower_bound(H,H+cnt,x)-H;}
10int n,m;
11int tot;//线段树的总数。
12int root[N];//每个元素对应的根节点
13struct PTree
14{
15 int sum,left,right;
16}tree[N*30];
17inline int add_node( int _sum,int _left,int _right)
18{
19 int idx = ++tot;
20 tree[idx].sum = _sum;
21 tree[idx].left = _left;
22 tree[idx].right = _right;
23 return idx;
24}
25void Insert( int &root,int pre_rt,int pos,int l,int r)
26{
27 root = add_node(tree[pre_rt].sum + 1,tree[pre_rt].left,tree[pre_rt].right);
28 //printf("l:%d r %d root:%d\n",l,r,root);
29 if (l==r) return;
30 int mid = (l+r)>>1;
31 if (pos<=mid)
32 Insert(tree[root].left,tree[pre_rt].left,pos,l,mid);
33 else
34 Insert(tree[root].right,tree[pre_rt].right,pos,mid+1,r);
35}
36int Query( int L,int R,int l,int r,int k)//区间第k大
37{
38 if (l==r) return l;
39 int mid = (l+r)>>1;
40 int sum = tree[tree[R].left].sum - tree[tree[L].left].sum;
41 //sum表示 左区间的元素个数
42 if (k<=sum)
43 return Query(tree[L].left,tree[R].left,l,mid,k);
44 else return Query(tree[L].right,tree[R].right,mid+1,r,k-sum);
45}
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("./in.txt","r",stdin);
5 #endif
6 int T;
7 cin>>T;
8 while (T--){
9 tot = 0 ;
10 scanf("%d%d",&n,&m);
11 for ( int i = 1 ; i <= n ; i++) scanf("%d",a+i),H[i] = a[i];
12 root[0] = 0;
13 sort(H+1,H+n+1);
14 cnt = unique(H+1,H+n+1)-(H+1);
15 for ( int i = 1; i <= n ; i++)
16 {
17 int pos = Hash(a[i]);
18 //printf("pos:%d\n",pos);
19 Insert(root[i],root[i-1],pos,1,cnt);
20 //cout<<"i"<<i<<endl;
21 }
22 while (m--)
23 {
24 int l,r,k;
25 scanf("%d %d %d",&l,&r,&k);
26 int pos = Query(root[l-1],root[r],1,cnt,k);
27 printf("%d\n",H[pos]);
28 }
29 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}