AT_abc421_f [ABC421F] Erase between X and Y

有一个序列 $A$。起始时，$A=(0)$。也就是说，$A$ 是一个长度为 $1$ 且唯一元素为 $0$ 的序列。 你需要依次处理 $Q$ 个操作。第 $i$ 个操作（$1\leq i\leq Q$）有如下两种形式之一： - `1 x`：在 $A$ 中 $x$ 出现的位置后面插入 $i$。具体地，记当前 $A$ 的第 $j$ 个元素为 $A_j$，$n$ 为 $A$ 当前长度。若 $A_p=x$，则更新 $A$ 为 $(A_1,\dots,A_p,i,A_{p+1},\dots,A_n)$。保证本操作处理前 $A$ 中必然包含 $x$。 - `2 x y`：删除 $A$ 中 $x$ 和 $y$ 之间的所有元素，并输出被删除元素的和。具体地，记当前 $A$ 的第 $j$ 个元素为 $A_j$，$n$ 为 $A$ 当前长度。若 $A_p=x$，$A_q=y$，则输出 $A_{\min(p,q)+1} + \dots + A_{\max(p,q)-1}$，并将 $A$ 更新为 $(A_1,\dots,A_{\min(p,q)},A_{\max(p,q)},\dots,A_n)$。保证本操作处理前 $A$ 中必然包含 $x$ 与 $y$。 注意，对于任意一组操作序列，在处理操作过程中，A 中同样的值不会重复出现，因此某个值在 $A$ 中的位置是唯一的（如果它存在的话）。

输入按如下格式从标准输入读入： >$Q$ >$\text{query}_{1}$ >$\text{query}_{2}$ >$\vdots$ >$\text{query}_{Q}$ 其中，$\text{query}_{i}$ 表示第 $i$ 个操作，为下述两种格式之一： >1 $x$ >2 $x$ $y$

设一共有 $q$ 个 $2$ 类型操作。请输出 $q$ 行，第 $i$ 行输出第 $i$ 个 $2$ 类型操作的输出结果。

### 样例解释 1 初始时，$A=(0)$。 - 第 $1$ 次操作：在 $0$ 后插入 $1$。$A$ 变为 $(0,1)$。 - 第 $2$ 次操作：在 $1$ 后插入 $2$。$A$ 变为 $(0,1,2)$。 - 第 $3$ 次操作：在 $0$ 后插入 $3$。$A$ 变为 $(0,3,1,2)$。 - 第 $4$ 次操作：删除 $2$ 和 $3$ 之间的元素，也就是 $1$，输出 $1$。$A$ 变为 $(0,3,2)$。 - 第 $5$ 次操作：在 $2$ 后插入 $5$。$A$ 变为 $(0,3,2,5)$。 - 第 $6$ 次操作：删除 $0$ 和 $5$ 之间的元素，即 $3,2$，输出 $5$。$A$ 变为 $(0,5)$。 ### 样例解释 2 第 $2$ 次操作中，删除 $0$ 和 $1$ 之间的元素，但它们之间其实没有元素，所以输出 $0$。 ### 数据范围 - $1 \le Q \le 5\times 10^5$ - 对于第 $i$ 个操作： - 若为 $1$ 类型操作： - $0 \le x < i$ - 操作前 $A$ 中一定包含 $x$。 - 若为 $2$ 类型操作： - $0\le x < y < i$ - 操作前 $A$ 中一定包含 $x$ 和 $y$。 - 所有输入均为整数。 由 ChatGPT 5 翻译