学步园

传送门：【codeforces】484E. Sign on Fence

题目分析：看了题解才会呢，感觉太巧妙了~

先对高度从高到低排序，然后构造可持久化线段树，每个节点保存一个高度下对应区间的左连续最大1个数，右连续最大1个数，区间最长连续1个数，然后查询一个区间内最长连续1长度就是线段树区间合并操作。每次询问【L，R，W】就是二分询问的高度（每个高度是一棵线段树），然后看询问区间的连续1个数是否大于等于W，大于就调整上界，否则调整下界（下标小的高度大，这样处理的好处是二分可以很轻易的写出来，直接就是lower_bound）。

不得不叹服啊，自己想了好一会儿也没想到可以转化成连续1来搞。。。

路还很长呢~

代码如下：

#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std ;

typedef long long LL ;

#define rep( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define mid ( ( l + r ) >> 1 )

const int MAXN = 100005 ;

struct Node {
	int h , pos ;
	bool operator < ( const Node& a ) const {
		return h > a.h ;
	}
} node[MAXN] ;

struct Segment_Tree* null ;
struct Segment_Tree {
	Segment_Tree* c[2] ;
	//int sum ;
	int Lmax ;
	int Rmax ;
	int Mmax ;
	inline void modify ( int val ) {
		c[0] = c[1] = null ;
		Lmax = Mmax = Rmax = val ;
	}
	inline void push_up ( int l , int r ) {
		int m = mid ;
		//sum = c[0]->sum + c[1]->sum ;
		Lmax = c[0]->Lmax ;
		Rmax = c[1]->Rmax ;
		Mmax = max ( max ( c[0]->Mmax , c[1]->Mmax ) , c[0]->Rmax + c[1]->Lmax ) ;
		if ( Lmax == m - l + 1 ) Lmax += c[1]->Lmax ;
		if ( Rmax == r - m ) Rmax += c[0]->Rmax ;
	}
} ;

Segment_Tree pool[MAXN * 50] ;
Segment_Tree* cur ;
Segment_Tree* Root[MAXN] ;
int n ;

void init () {
	cur = pool ;
	null = cur ++ ;
	null->modify ( 0 ) ;
}

void build ( Segment_Tree* &o , int l , int r ) {
	o = cur ++ ;
	o->modify ( 0 ) ;
	if ( l == r ) return ;
	int m = mid ;
	build ( o->c[0] , l , m ) ;
	build ( o->c[1] , m + 1 , r ) ;
}

void insert ( Segment_Tree* old , Segment_Tree* &now , int pos , int l , int r ) {
	now = cur ++ ;
	if ( l == r ) {
		now->modify ( 1 ) ;
		return ;
	}
	int m = mid ;
	if ( pos <= m ) {
		now->c[1] = old->c[1] ;
		insert ( old->c[0] , now->c[0] , pos , l , m ) ;
	} else {
		now->c[0] = old->c[0] ;
		insert ( old->c[1] , now->c[1] , pos , m + 1 , r ) ;
	}
	now->push_up ( l , r ) ;
}

int query ( Segment_Tree* o , int L , int R , int l , int r ) {
	if ( L <= l && r <= R ) return o->Mmax ;
	int m = mid ;
	if ( R <= m ) return query ( o->c[0] , L , R , l , m ) ;
	if ( m <  L ) return query ( o->c[1] , L , R , m + 1 , r ) ;
	int ans = max ( query ( o->c[0] , L , R , l , m ) , query ( o->c[1] , L , R , m + 1 , r ) ) ;
	ans = max ( ans , min ( o->c[0]->Rmax , m - L + 1 ) + min ( o->c[1]->Lmax , R - m ) ) ;
	return ans ;
}

int search ( int L , int R , int w ) {
	int l = 1 , r = n ;
	while ( l < r ) {
		int m = mid ;
		if ( query ( Root[m] , L , R , 1 , n ) >= w ) r = m ;
		else l = m + 1 ;
	}
	return node[l].h ;
}

void solve () {
	int l , r , w , m ;
	init () ;
	For ( i , 1 , n ) {
		scanf ( "%d" , &node[i].h ) ;
		node[i].pos = i ;
	}
	sort ( node + 1 , node + n + 1 ) ;
	build ( Root[0] , 1 , n ) ;
	For ( i , 1 , n ) {
		insert ( Root[i - 1] , Root[i] , node[i].pos , 1 , n ) ;
	}
	scanf ( "%d" , &m ) ;
	while ( m -- ) {
		scanf ( "%d%d%d" , &l , &r , &w ) ;
		printf ( "%d\n" , search ( l , r , w ) ) ;
	}
}


int main () {
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}