Skip to content

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;
}