本文主要是介绍【codeforces】484E. Sign on Fence 可持久化线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【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 ;
}这篇关于【codeforces】484E. Sign on Fence 可持久化线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
