14225: 【原4225】MoLe的栈
题目
题目描述
author: MoLe 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4225
Description
MoLe有一个普通的栈，他在这个栈上进行了\(m\)次合法的操作（即仅包含合法的push一个正整数到栈顶和pop栈顶的元素）。但是不幸的是，由于长期饱受多项大作业的折磨，MoLe患上了间歇性记忆紊乱症，MoLe记得自己所做过的每一件事情，但是并不能够以一个正确的顺序将自己做过的事情回忆起来。体现在这个栈上，MoLe会在第\(i\)时刻记起自己过去在第\(p_i\)时刻的操作（显然\(p_i\)是一个\(1 \sim m\)的排列），即向栈顶压入一个正整数或在栈非空的情况下将栈顶元素弹出。现在MoLe想知道在每一时刻，执行完所有自己回忆起的操作后（按照操作时的顺序）栈顶的元素是什么。
Input Format
第一行一个整数\(m\)，代表MoLe所进行的总操作次数
接下来\(m\)行，第\(i\)行代表MoLe在第\(i\)时刻所回忆起的操作
第一个整数\(p_i\)代表该操作原来的是第几个被执行的操作，接下来一个整数\(t_i\),\(t_i\)为\(0\)代表该操作为弹出，\(t_i\)为\(1\)则后面还有一个正整数\(x_i\)，代表将\(x_i\)压入栈顶。数据保证总操作合法，*注意仅执行回忆起的前若干步操作会出现弹出次数大于压入的情况，此时视为栈内没有元素
Output Format
输出共\(m\)行，每行一个整数，代表仅执行回忆起的前\(i\)步操作后栈顶的元素，若栈内没有元素，则输出\(-1\)
Sample Input
4
4 0
1 1 2
2 1 3
3 0
Sample Output
-1
-1
3
-1
Limit
对于\(40 \% \)的数据，\(m \leq 10^3\)
对于\(100 \% \)的数据，\(m \leq 10^5, x_i \leq 10^6\)
zqy2018's solution
/*
See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4225.md
*/
#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
int read(){
int f = 1, x = 0;
char c = getchar();
while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, siz;
set<pair<int, int> > st[263000];
int lft[263000] = {0};
const int INF = 0x3f3f3f3f;
void update(int k, int o){
int id = k;
int tp = 1, isr, lch, rch;
pair<int, int> p(id, o);
k += siz - 1;
if (o == INF) ++lft[k];
else st[k].insert(p);
int invl = id, invr = id, len = 1;
while (k > 1){
isr = (k & 1), k >>= 1;
lch = k << 1, rch = k << 1 | 1;
if (isr) invl -= len;
else invr += len;
len <<= 1;
// cout << k << " " << isr << " " << tp << " " << p.first << " " << p.second << endl;
if (tp == 1){
// add
if (isr){
if (p.second == INF){
if (st[lch].size() <= lft[rch] - 1){
// 不够抵消
++lft[k];
}else {
// 直接除去还在栈中的左边的部分
int mid = (invl + invr + 1) >> 1;
auto iter = st[k].lower_bound(make_pair(mid, -INF));
--iter;
auto pp = *iter;
// 找到仍在栈中的
st[k].erase(pp);
tp = -1, p = pp;
}
}else {
// 直接加入即可
st[k].insert(p);
}
}else {
if (p.second == INF){
// 直接作为无法抵消的部分
++lft[k];
}else {
if (lft[rch] == 0){
// 直接加入
st[k].insert(p);
}else {
// 需要和被抵消的交换
if (st[lch].size() > lft[rch] + 1){
// 有余留
int mid = (invl + invr + 1) >> 1;
auto iter = st[k].lower_bound(make_pair(mid, -INF));
--iter;
auto iter2 = st[lch].find(*iter);
++iter2;
auto pp = *iter2;
// cout << endl << pp.first << endl;
// 找到原来被抵消的那个，比较确定新增者
if (p.first > pp.first){
// 新的被抵消了，原来的恢复
p = pp;
}
st[k].insert(p);
}else if (st[lch].size() == lft[rch] + 1){
// 之前刚好抵消
auto pp = *st[lch].begin();
st[k].insert(pp), p = pp;
}else {
// 之前也没有抵消
--lft[k];
tp = -1, p.second = INF;
}
}
}
}
}else {
// remove
if (isr){
if (p.second == INF){
if (st[lch].size() <= lft[rch]){
// 无济于事
--lft[k];
}else if (st[lch].size() == lft[rch] + 1){
// 之前完全抵消，现在左边有余量
auto pp = *st[lch].begin();
st[k].insert(pp);
tp = 1, p = pp;
}else {
// 左侧余量加一
int mid = (invl + invr + 1) >> 1;
auto iter = st[k].lower_bound(make_pair(mid, -INF));
--iter;
// 找到之前栈顶的下一个，恢复
auto iter2 = st[lch].find(*iter);
++iter2;
auto pp = *iter2;
// 将恢复的重新放入
st[k].insert(pp);
tp = 1, p = pp;
}
}else {
// 直接删除
st[k].erase(p);
}
}else {
if (p.second == INF){
// remove unused
--lft[k];
}else {
if (st[lch].size() >= lft[rch]){
// 之前有余量
int mid = (invl + invr + 1) >> 1;
auto iter = st[k].lower_bound(make_pair(mid, -INF));
--iter;
auto pp = *iter;
if (p.first > pp.first){
p = pp;
}
st[k].erase(p);
}else {
++lft[k];
tp = 1, p.second = INF;
}
}
}
}
}
}
void init(){
n = read();
for (siz = 1; siz < n; siz <<= 1)
;
}
void solve(){
REP(i, 1, n){
int p = read(), o = read();
if (o == 1) {
int x = read();
update(p, x);
}else {
update(p, INF);
}
if (st[1].empty()){
printf("-1\n");
}else{
printf("%d\n", st[1].rbegin()->second);
}
}
}
int main(){
init();
solve();
return 0;
}