题目：AT_abc273_e
题意
-
有空序列 \(a\)，另外有 \(10^9\) 个空序列 \(p1 \sim p_{10^9}\)，现在执行 \(q\) 次操作，包括以下四种操作：
ADD x，在序列 \(a\) 后插入整数 \(x\)。DELETE，删除 \(a\) 的末尾元素，空则什么都不干。SAVE y，赋值操作，\(p_x = a\)。LODE z，将 \(a\) 变为 \(p_z\)。
-
每次操作后输出 \(a\) 的末尾元素，没有输出 \(-1\)。
-
数据范围：\(1 \le q \le 5 \times 10^5, 1 \le x,y,z \le 10^9\)。
思路
-
显然有一个暴力，模拟操作，肯定超时。
-
首先我们肯定不能把整个序列存下来，但是有些元素删除了，\(LODE\) 后可能又恢复了，那该怎么办呢？
-
我们可以考虑一个树形结构，令 \(nx\) 为当前 \(a\) 的末尾元素，\(pos_y\) 表示 \(p_y\) 的末尾元素，那么插入元素就是将 \(fa_x = nx, nx = x\)，删除就是 \(nx = fa_{nx}\)，第三种操作，就是将 \(pos_y = nx\)，最后一种就是 \(nx = pos_z\)。
时间复杂度
- 因为 \(p\) 要用 \(map\)，\(O(\log 10^9)\)，其他每次均是 \(O(1)\)。
- \(q\) 组询问，共 \(O(q \log 10^9)\)。