本文主要是介绍【HDU】4967 Handling the Past 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【HDU】4967 Handling the Past
题目分析：比赛的时候没机会看这道题，没想到是线段树。。。
题目的意思是每给一个操作，然后就将这个操作和之前的操作按时间重新排序后重新执行，然后如果是peak就输出重新执行后对应时间的栈顶元素。保证没有非法pop操作。
首先我们可以将时间离散化（题目保证时间不同），按照离散化的时间建立线段树。每次push操作向线段树对应时间的位置插入+1，每次pop操作向对应时间的位置插入-1。
然后就是关键的查询操作。设查询的时间为t，我们知道如果要找到栈顶元素，那么就要找到最大的t'使得[t',t]内的元素和大于0（也就是push操作大于pop），最大的t'一定是当push操作正好比pop操作大1时的位置。那么我们该怎么才能找到这个位置？
为了能够实现这个操作我们需要两个数组分别记录区间和sum以及区间的最大后缀和maxs。
首先按照线段树的区间查询查找到区间[1,t]，然后在这个区间内优先查找右边的区间[L,R]，如果满足[L,R]的maxs+sum{[R+1,t]}>0则确定最大的t'一定在这个区间内。否则，向左边的区间继续寻找。sum[L,t]就是[L,t]的子区间的区间和的和，用一个元素v就可以记录当前区间[L,R]后面sum{[R+1,t]}的值，并且在这个区间不满足条件的时候v再加上sum{[L,R]}就能更新出sum{[L,t]}。
现在我们假设已经找到t'所在的区间，依旧用上述的方法寻找即可找到对应的位置了~~~
我觉得自己的语文水平还不如代码清晰，还是看代码容易理解。。。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#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 ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define rt o , l , r
#define root 1 , 1 , n
#define mid ( ( l + r ) >> 1 )const int MAXN = 50005 ;
const int INF = 0x3f3f3f3f ;struct Node {int val ;int time ;int opp ;int idx ;
} a[MAXN] ;int sum[MAXN << 2] ;
int maxs[MAXN << 2] ;
int val[MAXN] ;
char s[10] ;
int n ;
int ans ;void pushup ( int o ) {sum[o] = sum[ls] + sum[rs] ;if ( maxs[ls] + sum[rs] > maxs[rs] ) maxs[o] = maxs[ls] + sum[rs] ;else maxs[o] = maxs[rs] ;
}void update ( int v , int pos , int o , int l , int r ) {if ( l == r ) {maxs[o] = sum[o] = v ;return ;}int m = mid ;if ( pos <= m ) update ( v , pos , lson ) ;else update ( v , pos , rson ) ;pushup ( o ) ;
}void get ( int v , int o , int l , int r ) {if ( l == r ) {ans = val[l] ;return ;}int m = mid ;if ( v + maxs[rs] > 0 ) get ( v , rson ) ;else get ( v + sum[rs] , lson ) ;
}void query ( int& v , int L , int R , int o , int l , int r ) {if ( ~ans ) return ;if ( L <= l && r <= R ) {if ( v + maxs[o] <= 0 ) v += sum[o] ;else get ( v , o , l , r ) ;return ;}int m = mid ;if ( m < R ) query ( v , L , R , rson ) ;if ( L <= m ) query ( v , L , R , lson ) ;
}int cmp1 ( const Node& a , const Node& b ) {return a.time < b.time ;
}int cmp2 ( const Node& a , const Node& b ) {return a.idx < b.idx ;
}void scanf ( int& x , char c = 0 ) {while ( ( c = getchar () ) < '0' || c > '9' ) ;x = c - '0' ;while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ;
}void scanf ( char buf[] , char c = 0 , int top = 0 ) {while ( ( c = getchar () ) == ' ' || c == '\n' ) ;buf[top ++] = c ;while ( ( c = getchar () ) != ' ' && c != '\n' ) buf[top ++] = c ;buf[top] = 0 ;
}void solve () {CLR ( sum , 0 ) ;CLR ( maxs , -INF ) ;FOR ( i , 1 , n ) {scanf ( s ) ;if ( s[1] == 'u' ) {scanf ( a[i].val ) ;a[i].opp = 0 ;}else if ( s[1] == 'o' ) a[i].opp = 1 ;else a[i].opp = 2 ;scanf ( a[i].time ) ;a[i].idx = i ;}sort ( a + 1 , a + n + 1 , cmp1 ) ;FOR ( i , 1 , n ) a[i].time = i , val[i] = a[i].val ;sort ( a + 1 , a + n + 1 , cmp2 ) ;FOR ( i , 1 , n ) {if ( a[i].opp == 0 ) update ( 1 , a[i].time , root ) ;else if ( a[i].opp == 1 ) update ( -1 , a[i].time , root ) ;else {int v = 0 ;ans = -1 ;query ( v , 1 , a[i].time , root ) ;printf ( "%d\n" , ans ) ;}}
} int main () {int cas = 0 ;while ( ~scanf ( "%d" , &n ) && n ) {printf ( "Case #%d:\n" , ++ cas ) ;solve () ;}return 0 ;
} 这篇关于【HDU】4967 Handling the Past 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
