## 【POJ】2104 K-th Number 静态第K小——主席树

2017年11月20日 ⁄ 综合 ⁄ 共 2174字 ⁄ 字号 评论关闭

```#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 ;
else
l = 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 ;
}```