静态区间第k大的问题，往往可以利用主席树来解决
这是主席树的第一道题
主席树大概可以理解为在n个节点上都建立一棵线段树，但是想想会超出内存
每一个节点保存的线段树都记录当前整段前缀区间的信息
但是因为每次添加后一个节点，那么他除了当前节点位置需要更新之外，其他的位置都可以保持跟上一棵节点对应的线段树一致，那么为了缩小内存，
将那些不需要改变的点的指针指向上一棵树对应的节点即可，其他多生成的节点也就是需要更新的节点，最多不超过log2n个，所以最后产生的线段树的
点的个数大概在nlogn的大致范围内
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6 #define N 100005 7 #define M int m=(l+r)>>1 8 #define LS(o) node[o].ls 9 #define RS(o) node[o].rs 10 11 int n , m , a[N] , b[N] , T[N]; 12 13 struct Node{ 14 int sz , ls , rs; 15 void init(){sz=0;ls=rs=0;} 16 }node[N*30]; 17 18 int tot; 19 20 int build(int l , int r) 21 { 22 int u = tot++; 23 node[u].init(); 24 if(l!=r){ 25 M; 26 node[u].ls = build(l , m); 27 node[u].rs = build(m+1 , r); 28 } 29 return u; 30 } 31 32 void build(int o1 , int o2 , int l , int r , int pos) 33 { 34 node[o2].init(); 35 node[o2].sz = node[o1].sz+1; 36 M; 37 if(l == r) return; 38 if(pos<=m){ 39 node[o2].ls = tot++ , node[o2].rs = RS(o1); 40 build(LS(o1) , LS(o2) , l , m , pos); 41 } 42 else { 43 node[o2].rs = tot++ , node[o2].ls = LS(o1); 44 build(RS(o1) , RS(o2) , m+1 , r , pos); 45 } 46 } 47 48 int query(int o1 , int o2 , int l , int r , int k) 49 { 50 if(l==r) return l; 51 M; 52 int tmp; 53 if((tmp=node[LS(o2)].sz - node[LS(o1)].sz)>=k) return query(LS(o1) , LS(o2) , l , m , k); 54 else return query(RS(o1) , RS(o2) , m+1 , r , k-tmp); 55 } 56 57 int main() 58 { 59 // freopen("in.txt" , "r" , stdin); 60 while(~scanf("%d%d" , &n , &m)){ 61 for(int i=1 ; i<=n ; i++)scanf("%d" , a+i); 62 for(int i=1 ; i<=n ; i++)b[i]=a[i]; 63 sort(b+1 , b+n+1); 64 tot = 0; 65 T[0] = build(1 , n); 66 for(int i=1 ; i<=n ; i++){ 67 int pos = lower_bound(b+1 , b+n+1 , a[i])-b; 68 T[i] = tot++; 69 build(T[i-1] , T[i] , 1 , n , pos); 70 } 71 while(m--){ 72 int s , t , k; 73 scanf("%d%d%d" , &s , &t , &k); 74 int pos = query(T[s-1] , T[t] , 1 , n , k); 75 printf("%d " , b[pos]); 76 } 77 } 78 return 0; 79 }