学步园

传送门：【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 ;
}