Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 273 E問題 Notebook

AtCoder ABC273 ABC E問題 500 pts

問題

提出解答

問題の概要

空数列 $A$ と長さ $10^9$ の整数列の列 $\mathcal{E}:=(E_1, \dots, E_{10^9})$ がある. $\mathcal{E}$ の各項は空列である.

次の $Q$ 個のクエリを順に処理せよ.

${\tt ADD}~x$ : $A$ の末尾に $x$ を加える.
${\tt DELETE}$ : $A$ の末尾を削除する. ただし, $A$ が空列の場合は何もしない.
${\tt SAVE}~y$ : $E_y \gets A$
${\tt LOAD}~z$ : $A \gets E_z$

各クエリ終了後における $A$ の末尾を求めよ. なお, $A$ が空列だった場合は $-1$ とする.

制約

$1 \leq Q \leq 5 \times 10^5$
$1 \leq x,y,z \leq 10^9$

解法

$A$ の履歴を木で考えることにする.

次のように考える.

頂点 $0$ にマーカー $1,2, \dots, 10^9$ がある. また, ポインタが頂点 $0$ にある. また, 頂点 $0$ に整数 $-1$ を書き込む.
各クエリごとに次のように処理する.
- ${\tt ADD}~x$ : 今いる頂点を親に持つ子を1つ生成する. 子には整数 $x$ を書き込み, ポインタを子に移動させる.
- ${\tt DELETE}$ : 今いる頂点が $0$ でなければ, ポインタを親に移動させる.
- ${\tt SAVE}~y$ : マーカー $y$ を今ポインタがいる頂点に移動させる.
- ${\tt LOAD}~z$ : ポインタをマーカー $z$ がある頂点に異動させる.
ポインタがある頂点に書かれている整数が末尾の項 (空列の場合にはポインタが根にあるので, そこに書き込まれている整数は $-1$ であるから, 実は空列の場合も場合分けの必要がなくなる).

これにより, 計算量 $O(N)$ 時間で解くことが出来る.