主席树

区间第k大，不修改模板
 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <vector>
 5 using namespace std;
 6 
 7 const int maxn = 1e5 + 7;
 8 
 9 struct trie{
10     int cnt,root[maxn];
11 
12     struct node{
13         int l,r,sum;
14     }T[maxn*40];
15 
16     vector < int > v;
17 
18     void init(int *num,int n){//离散化+初始化
19         cnt = 0;
20         v.clear();
21         for(int i=1;i<=n;i++){
22             v.push_back(num[i]);
23             root[i] = 0;
24         }
25         sort(v.begin(),v.end());
26         v.erase(unique(v.begin(),v.end()),v.end());
27         for(int i=1;i<=n;i++){
28             update(1,n,root[i],root[i-1],getid(num[i]));
29         }
30     }
31 
32     int getid(int x){
33         return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
34     }
35 
36     void update(int l,int r,int &x,int y,int pos){
37         T[++cnt] = T[y];
38         T[cnt].sum ++;
39         x = cnt;
40         if(l == r) return;
41         int mid = (l+r)>>1;
42         if(mid >= pos) update(l,mid,T[x].l,T[y].l,pos);
43         else update(mid+1,r,T[x].r,T[y].r,pos);
44     }
45 
46     int query(int l,int r,int x,int y,int k){
47         if(l == r) return l;
48         int mid = (l+r)>>1;
49         int sum = T[T[y].l].sum - T[T[x].l].sum;
50         if(sum >= k) return query(l,mid,T[x].l,T[y].l,k);
51         else return query(mid+1,r,T[x].r,T[y].r,k-sum);
52     }
53 }tree;
54 
55 int num[maxn];
56 
57 int main(){
58     int n,m;
59     int t;
60     scanf("%d",&t);
61     while(t--){
62         scanf("%d%d",&n,&m);
63         for(int i=1;i<=n;i++)
64             scanf("%d",&num[i]);
65         tree.init(num,n);
66         int l,r,k;
67         while(m--){
68             scanf("%d%d%d",&l,&r,&k);
69             printf("%d
",tree.v[tree.query(1,n,tree.root[l-1],tree.root[r],k)-1]);
70         }
71     }
72     return 0;
73 }