Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：#
求区间第k大数
思路：#
可持久化线段树。
其实这东西在国内更常见的名字应该是 zhu xi 树？应该是由于“中国高端数据结构领导者”的hjt比较早得引入（？推广？）而得来的。
不过之前没写什么东西都被封，写个zhu xi 树，怕是政治敏感够枪毙100回了orz
似乎也叫函数式线段树。
写个模板题练下手。学习笔记之后补。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2017年10月16日 星期一 21时51分55秒
4File Name :2104.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=1E5+7;
35int a[N],H[N];
36int cnt;
37int Hash( int x){ return lower_bound(H,H+cnt,x)-H;}
38int n,m;
39int tot;//线段树的总数。
40int root[N];//每个元素对应的根节点
41struct PTree
42{
43 int sum,left,right;
44}tree[N*30];
45inline int add_node( int _sum,int _left,int _right)
46{
47 int idx = ++tot;
48 tree[idx].sum = _sum;
49 tree[idx].left = _left;
50 tree[idx].right = _right;
51 return idx;
52}
53void Insert( int &root,int pre_rt,int pos,int l,int r)
54{
55 root = add_node(tree[pre_rt].sum + 1,tree[pre_rt].left,tree[pre_rt].right);
56 //printf("l:%d r %d root:%d\n",l,r,root);
57 if (l==r) return;
58 int mid = (l+r)>>1;
59 if (pos<=mid)
60 Insert(tree[root].left,tree[pre_rt].left,pos,l,mid);
61 else
62 Insert(tree[root].right,tree[pre_rt].right,pos,mid+1,r);
63}
64int Query( int L,int R,int l,int r,int k)//区间第k大
65{
66 if (l==r) return l;
67 int mid = (l+r)>>1;
68 int sum = tree[tree[R].left].sum - tree[tree[L].left].sum;
69 //sum表示 左区间的元素个数
70 if (k<=sum)
71 return Query(tree[L].left,tree[R].left,l,mid,k);
72 else return Query(tree[L].right,tree[R].right,mid+1,r,k-sum);
73}
74
75
76
77int main()
78{
79 #ifndef ONLINE_JUDGE
80 freopen("./in.txt","r",stdin);
81 #endif
82 int T;
83 cin>>T;
84 while (T--){
85 tot = 0 ;
86 scanf("%d%d",&n,&m);
87 for ( int i = 1 ; i <= n ; i++) scanf("%d",a+i),H[i] = a[i];
88 root[0] = 0;
89 sort(H+1,H+n+1);
90 cnt = unique(H+1,H+n+1)-(H+1);
91 for ( int i = 1; i <= n ; i++)
92 {
93 int pos = Hash(a[i]);
94 //printf("pos:%d\n",pos);
95 Insert(root[i],root[i-1],pos,1,cnt);
96 //cout<<"i"<<i<<endl;
97 }
98 while (m--)
99 {
100 int l,r,k;
101 scanf("%d %d %d",&l,&r,&k);
102 int pos = Query(root[l-1],root[r],1,cnt,k);
103 printf("%d\n",H[pos]);
104 }
105 }
106
107
108 #ifndef ONLINE_JUDGE
109 fclose(stdin);
110 #endif
111 return 0;
112}