本文主要是介绍【POJ】2104 K-th Number 静态第K小——主席树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【POJ】2104 K-th Number
题目分析：
哇咔咔，又get了一个新技能——主席树，初步学习主席树，一次AC，感觉好棒~
也在此Orz一下发明者主席——fotile96，在叉姐群经常看到主席的身影，不过蒟蒻也只能仰望神犇的背影了，起步迟且天赋不如人，只能慢慢的走下去，希望有一天能看到另一个世界。
主席树的编程方式是函数式编程（可持久化），保证我们可以查询历史版本。且它的更新就是每次在上一次更新的线段树上再更新一条链。为每个需要更新的节点创建新的节点，不需要更新的节点直接指向上一棵树对应的位置即可。
主席树中的区间是原数组序列离散化并排好序的区间，主席树的每个节点需要维护一个值c，c表示在插入的数前面（包括这个数）有多少个不大于它的数。每插入一个值就需要更新一条链，然后维护一下c。
查询【L，R】区间内第K小的数时，就用已知的c来寻找这个数在排完序后的数组对应的位置，然后输出这个位置对应的大小就好了> <
根本描述不清楚> <，主席树太厉害啦，大家还是看代码来理解比较好。。。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REP_1( i , n ) for ( int i = 0 ; i <= n ; ++ i )
#define REV( i , n ) for ( int i = n - 1 ; i >= 0 ; -- i )
#define REV_1( i , n ) for ( int i = n ; i >= 0 ; -- i )
#define REPF( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define REPF_1( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a - 1 ; i >= b ; -- i )
#define REPV_1( i , a , b ) for ( int i = a ; i >= b ; -- i )#define CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )#define mid ( ( l + r ) >> 1 )const int MAXN = 100005 ;struct Seg_Tree {int Ls , Rs ;int c ;
} ;Seg_Tree T[MAXN * 21] ;
int A[MAXN] ;
int a[MAXN] ;
int idx ;
int Root[MAXN] ;
int cnt ;void build ( int &o , int l , int r ) {o = ++ idx ;T[o].c = 0 ;if ( l == r )return ;int m = mid ;build ( T[o].Ls , l , m ) ;build ( T[o].Rs , m + 1 , r ) ;
}int unique ( int a[] , int n ) {int cnt = 1 ;sort ( a + 1 , a + n + 1 ) ;REPF_1 ( i , 2 , n )if ( a[i] != a[cnt] )a[++ cnt] = a[i] ;return cnt ;
}int lower_bound ( int x , int l , int r ) {while ( l < r ) {int m = mid ;if ( a[m] >= x )r = m ;elsel = m + 1 ;}return l ;
}int insert ( int old , int key ) {int root = ++ idx , now = root ;int l = 1 , r = cnt ;T[now].c = T[old].c + 1 ;while ( l < r ) {int m = mid ;if ( key <= m ) {T[now].Ls = ++ idx ;T[now].Rs = T[old].Rs ;now = T[now].Ls ;old = T[old].Ls ;r = m ;}else {T[now].Ls = T[old].Ls ;T[now].Rs = ++ idx ;now = T[now].Rs ;old = T[old].Rs ;l = m + 1 ;}T[now].c = T[old].c + 1 ;}return root ;
}int query ( int old , int now , int kth ) {int l = 1 , r = cnt ;while ( l < r ) {int m = mid ;if ( kth <= T[T[now].Ls].c - T[T[old].Ls].c ) {now = T[now].Ls ;old = T[old].Ls ;r = m ;}else {kth -= T[T[now].Ls].c - T[T[old].Ls].c ;now = T[now].Rs ;old = T[old].Rs ;l = m + 1 ;}}return l ;
}int n , m , q ;void solve () {int l , r , k ;cnt = 0 ;REPF_1 ( i , 1 , n ) {scanf ( "%d" , &A[i] ) ;a[++ cnt] = A[i] ;}cnt = unique ( a , cnt ) ;idx = 0 ;build ( Root[0] , 1 , cnt ) ;REPF_1 ( i , 1 , n ) {int x = lower_bound ( A[i] , 1 , cnt + 1 ) ;Root[i] = insert ( Root[i - 1] , x ) ;}while ( q -- ) {scanf ( "%d%d%d" , &l , &r , &k ) ;printf ( "%d\n" , a[query ( Root[l - 1] , Root[r] , k )] ) ;}
}int main () {while ( ~scanf ( "%d%d" , &n , &q ) )solve () ;return 0 ;
}这篇关于【POJ】2104 K-th Number 静态第K小——主席树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
