听说灌水区巨佬多 主席树求条

#include<bits/stdc++.h>
#include<map>
using namespace std ; 

const int N= 7e6 + 10 ; 
int dish[ N ] , title[ N ] , n , m , mape[ N ] ;
int sort_node[ N ] , tot = 1 ; 
map< int ,int  > h ; 
struct node 
{
	int data ; 
	int right ; 
	int left ; 
	int lo_left ; 
	int lo_right ; 
}dt[ N ] ; 
void build( int u , int l , int r ) 
{
	tot = max( tot , u ) ; 
	dt[ u ].right = r ; 
	dt[ u ].left = l ; 
	dt[ u ].data = 0 ; 
	if( l == r )
		return ; 
	dt[ u ].lo_right = u << 1 | 1 ;
	dt[ u ].lo_left	= u << 1 ; 
	int mid = l + r >> 1 ;
	build( u << 1 , l , mid ) ; 
	build( u << 1 | 1 , mid + 1 , r ) ;  
}

void add( int u1 , int u2 , int data ) 
{
	dt[ u2 ].left = dt[ u1 ].left ; 
	dt[ u2 ].right = dt[ u1 ].right ;
	dt[ u2 ].data = dt[ u1 ].data + 1 ; 
	if( dt[ u1 ].left == dt[ u1 ].right ) 
		return ; 
	int mid = dt[ u1 ].left + dt[ u1 ].right >> 1 ; 
	if( data <= mid ) 
	{
		dt[ u2 ].lo_right = dt[ u1 ].lo_right ; 
		dt[ u2 ].lo_left = ++ tot ; 
		add( dt[ u1 ].lo_left , dt[ u2 ].lo_left , data ) ; 
	} 
	else
	{
		dt[ u2 ].lo_left = dt[ u1 ].lo_left ; 
		dt[ u2 ].lo_right = ++ tot ; 
		add( dt[ u1 ].lo_right , dt[ u2 ].lo_right , data ) ; 
	}
}

int ask( int u1 , int u2 , int k )
{
	if( dt[ u1 ].left == dt[ u1 ].right ) 
		return dt[ u1 ].left ; 
	int mid = dt[ u2 ].data - dt[ u1 ].data ; 
	if( k >= mid ) return ask( dt[ u1 ].lo_right , dt[ u2 ].lo_right , k ) ;
	else return ask( dt[ u1 ].lo_left , dt[ u2 ].lo_left , k ) ; 
}

int main() 
{
	cin >> n >> m ; 
	for( int i = 1 ; i <= n ; i ++ ) 
	{
		cin >> dish[ i ] ; 
		sort_node[ i ] = dish[ i ] ; 
	}
	sort( sort_node + 1 , sort_node + 1 + n ) ; 
	int ko = 0 , tit = 0 ; 
	for( int i = 1 ; i <= n ; i ++ )
		if( ko != sort_node[ i ] ) 
		{
			ko = sort_node[ i ] ; 
			mape[ ++ tit ] = sort_node[ i ] ; 
			h.insert( make_pair( sort_node[ i ] , tit ) ) ; 
		}
	
	build( 1 , 1 , tit ) ; 
	title[ 0 ] = 1 ; 
	for( int i = 1 ; i <= n ; i ++ ) 
	{
		title[ i ] = ++ tot  ; 
		add( title[ i - 1 ] , title[ i ] , h[ dish[ i ] ] ) ; 
	}
	
	
	for( int i = 1 ; i <= m ; i ++ )
	{
		int l , r , k ; 
		scanf( "%d%d%d" , &l , &r , &k ) ; 
		cout << mape[ ask( title[ l - 1 ] , title[ r ] , k ) ] << endl ; 
	}
	
	return 0 ;  
}