problem

push(n) pop() の列で表されるプログラムが存在していた。 stackが空のときのpopは単に無視される。 Nikitaさんはこのプログラムを$1$度は全て忘れてしまったが、ある順番で$1$行ずつ思い出していく。 合計で$i$個の行まで思い出したとき、まだ思い出せていない行は空行と見做してプログラムを実行したときの最終的なstackのtopは何か。 それぞれの$i$について求めよ。

solution

区間加算と区間minのsegment木でstackの高さを管理する。$O(n \log n)$。

まずは空のときのpopが存在しないと仮定しよう。 各命令が終了した後のstackの高さを求めておけば、最終的な高さ$h$と等しい高さにするような最後のpush命令が答え。 これは高さが$h$でありそれ以降で高さが$h$未満になることがないような命令で最も最初のものを見付ければよい。 segment木と二分探索でいい感じにできる。

空のpopが問題だが、これを気にせず処理しても同じ方法で通る。

note

  • ある種の括弧の列と見ればnestの深さをsegtreeするのは典型
  • こういうの好き

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
using namespace std;

template <class Monoid, class OperatorMonoid>
struct lazy_propagation_segment_tree { // on monoids
    static_assert (is_same<typename Monoid::underlying_type, typename OperatorMonoid::target_type>::value, "");
    typedef typename Monoid::underlying_type underlying_type;
    typedef typename OperatorMonoid::underlying_type operator_type;
    const Monoid mon;
    const OperatorMonoid op;
    int n;
    vector<underlying_type> a;
    vector<operator_type> f;
    lazy_propagation_segment_tree() = default;
    lazy_propagation_segment_tree(int a_n, underlying_type initial_value = Monoid().unit(), Monoid const & a_mon = Monoid(), OperatorMonoid const & a_op = OperatorMonoid())
            : mon(a_mon), op(a_op) {
        n = 1; while (n <= a_n) n *= 2;
        a.resize(2 * n - 1, mon.unit());
        fill(a.begin() + (n - 1), a.begin() + ((n - 1) + a_n), initial_value); // set initial values
        REP_R (i, n - 1) a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]); // propagate initial values
        f.resize(max(0, (2 * n - 1) - n), op.identity());
    }
    void point_set(int i, underlying_type z) {
        assert (0 <= i and i < n);
        point_set(0, 0, n, i, z);
    }
    void point_set(int i, int il, int ir, int j, underlying_type z) {
        if (i == n + j - 1) { // 0-based
            a[i] = z;
        } else if (ir <= j or j+1 <= il) {
            // nop
        } else {
            range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);
            range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);
            f[i] = op.identity();
            point_set(2 * i + 1, il, (il + ir) / 2, j, z);
            point_set(2 * i + 2, (il + ir) / 2, ir, j, z);
            a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]);
        }
    }
    void range_apply(int l, int r, operator_type z) {
        assert (0 <= l and l <= r and r <= n);
        range_apply(0, 0, n, l, r, z);
    }
    void range_apply(int i, int il, int ir, int l, int r, operator_type z) {
        if (l <= il and ir <= r) { // 0-based
            a[i] = op.apply(z, a[i]);
            if (i < f.size()) f[i] = op.compose(z, f[i]);
        } else if (ir <= l or r <= il) {
            // nop
        } else {
            range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);
            range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);
            f[i] = op.identity();
            range_apply(2 * i + 1, il, (il + ir) / 2, l, r, z);
            range_apply(2 * i + 2, (il + ir) / 2, ir, l, r, z);
            a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]);
        }
    }
    underlying_type range_concat(int l, int r) {
        assert (0 <= l and l <= r and r <= n);
        return range_concat(0, 0, n, l, r);
    }
    underlying_type range_concat(int i, int il, int ir, int l, int r) {
        if (l <= il and ir <= r) { // 0-based
            return a[i];
        } else if (ir <= l or r <= il) {
            return mon.unit();
        } else {
            return op.apply(f[i], mon.append(
                    range_concat(2 * i + 1, il, (il + ir) / 2, l, r),
                    range_concat(2 * i + 2, (il + ir) / 2, ir, l, r)));
        }
    }
};
struct min_monoid {
    typedef int underlying_type;
    int unit() const { return INT_MAX; }
    int append(int a, int b) const { return min(a, b); }
};
struct plus_with_int_max_operator_monoid {
    typedef int underlying_type;
    typedef int target_type;
    int identity() const { return 0; }
    int apply(underlying_type a, target_type b) const { return b == INT_MAX ? INT_MAX : a + b; }
    int compose(underlying_type a, underlying_type b) const { return a + b; }
};

template <typename UnaryPredicate>
int64_t binsearch(int64_t l, int64_t r, UnaryPredicate p) {
    assert (l <= r);
    -- l;
    while (r - l > 1) {
        int64_t m = l + (r - l) / 2;  // avoid overflow
        (p(m) ? r : l) = m;
    }
    return r;
}

int main() {
    int n; scanf("%d", &n);
    vector<int> x(n + 2, -1);
    lazy_propagation_segment_tree<min_monoid, plus_with_int_max_operator_monoid> segtree(n + 2, 0);

    REP (i, n) {
        // input
        int p_i, t_i; scanf("%d%d", &p_i, &t_i);
        if (t_i) {  // push
            scanf("%d", &x[p_i]);
            segtree.range_apply(p_i, n + 2, +1);
        } else {  // pop
            segtree.range_apply(p_i, n + 2, -1);
        }

        // output
        int last_nest = segtree.range_concat(n + 1, n + 2);
        int j = binsearch(0, n + 2, [&](int j) {
            int min_nest = segtree.range_concat(j, n + 2);
            return last_nest <= min_nest;
        });
        printf("%d\n", x[j]);
    }
    return 0;
}