大意: 给定m个栈操作push(x)或pop(), 栈空时pop()无作用, 每个操作有执行的时间$t$, 对于每个$0 \le i \le m$, 输出[1,i]的栈操作按时间顺序执行后栈顶元素.
push看做1, pop看做-1, 线段维护后缀和, 栈顶即为第一个后缀和>0的位置
#include <iostream>
#include <algorithm>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define mid ((l+r)>>1)
#define lc (o<<1)
#define rc (lc|1)
#define ls lc,l,mid
#define rs rc,mid+1,r
using namespace std;const int N = 1e5+10, INF = 0x3f3f3f3f;
int m, ans, suf, a[N];
int s[N<<2], mx[N<<2];void update(int o, int l, int r, int pos, int v) {
if (l==r) return s[o]=mx[o]=v,void();
if (mid>=pos) update(ls,pos,v);
else update(rs,pos,v);
s[o] = s[lc]+s[rc];
mx[o] = max(mx[lc]+s[rc],mx[rc]);
}void query(int o, int l, int r) {
if (ans>0) return;
if (suf+mx[o]<=0) suf += s[o];
else if (l==r) ans = a[l];
else query(rs), query(ls);
}int main() {
scanf("%d", &m);
REP(i,1,m) {
int op, t, x;
scanf("%d%d", &t, &op);
if (op) {
scanf("%d", &x);
a[t] = x;
update(1,1,m,t,1);
} else update(1,1,m,t,-1);
ans = -1, suf = 0, query(1,1,m);
printf("%d\n", ans);
}
}