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 翻译