Codeforces #393 Div1 C. Nikita and stack

自力だと面倒なSegTree書いてたのでこの解法は参考になった。
http://codeforces.com/contest/759/problem/C

問題

スタックに整数をpushする命令とpopする命令が与えられる。
命令は全部でN個あるが、それぞれどの順で行われたか忘れてしまった。

i番目に記述されたpushまたはpop命令は、P[i]番に行われたとする。

1～Nの各mについて、先頭m個に書かれた命令をP[i]昇順に実行したとき、最後にスタックの最上位に来る数値を応えよ。

解法

命令列を逆にたどることを考える。
popをスタック長を-1、pushをスタック長を+1する命令と考える。
命令列を逆にたどった際初めてスタック長が正になったとき、その時pushした値が解になる。

では初めてスタック長が正になるタイミングをどう求めるか。
SegTreeを用い、区間の累積和と最大値を求められるようにしておき、初めて最大値が1となる位置を求めればよい。

int N;
const int NV=1<<19;
ll sum[2*NV], ma[2*NV];
int V[202020];


void add(int cur,int v) {
	cur += NV;
	sum[cur]=ma[cur]=v;
	while(cur>1) cur>>=1, sum[cur]=sum[2*cur]+sum[2*cur+1], ma[cur]=max(ma[2*cur],sum[2*cur]+ma[2*cur+1]);
}

int query(int cur,ll tot=0) {
	while(cur<NV) {
		cur*=2;
		if(ma[cur]<=tot) tot-=sum[cur], cur++;
	}
	return cur-NV;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>j;
		x = N+1-x;
		if(j==1) {
			cin>>V[x];
			add(x,1);
		}
		else {
			add(x,-1);
		}
		if(ma[1]<=0) cout<<-1<<endl;
		else cout<<V[query(1)]<<endl;;
	}
	
	
}

まとめ

これ本番出てたら面倒なSegTree書いてだいぶ手間取ってたな。