分数: 525 点
问题陈述
有一个序列 A。 最初, A=(0)。 (也就是说, A 是一个长度序列 1 包含 0 作为其唯一元素)。
你被给予 Q 查询按顺序处理。 的 i第一个查询 (1\leq i\leq Q) 具有以下形式之一:
1 x:插入 i 紧接在所在位置之后 x 出现在 A。 具体来说,让 A_j 是 j当前的第一个元素 A 和 n 的长度 A。对于 p 这样 A_p=x,更新 A to (A_1,\dots,A_p,i,A_{p+1},\dots,A_n)。 可以保证 A 包含 x 在处理此查询之前。2 x y:删除之间的所有元素 x 和 y in A,并输出移除元素的值的总和。 具体来说,让 A_j 是 j当前的第一个元素 A 和 n 的长度 A。对于 p 和 q 这样 A_p=x 和 A_q=y,输出 A_{\min(p,q)+1} + \dots + A_{\max(p,q)-1} 和 更新 A to (A_1,\dots,A_{\min(p,q)},A_{\max(p,q)},\dots,A_n)。 可以保证 A 包含两者 x 和 y 在处理此查询之前。
请注意,对于任何查询序列,相同的值永远不会在 A 在处理查询的过程中,因此值出现的位置 A 是唯一的(如果存在)。
约束
- 1\leq Q \leq 5\times 10^5
- 对于 i第一个查询:
- 如果是类型 1 查询:
- 0\leq x < i
- A 包含 x 在处理查询之前。
- 如果是类型 2 查询:
- 0\leq x < y < i
- A 包含两者 x 和 y 在处理查询之前。
- 如果是类型 1 查询:
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
6 1 0 1 1 1 0 2 2 3 1 2 2 0 5
示例输出 1
1 5
最初, 黑板上写着 A=(0).
- 1st 查询:插入 1 紧接着 0. A 变为 分别为 (0,1).
- 2第一个查询:插入 2 紧接着 1. A 变为 分别为 (0,1,2).
- 3rd 查询:插入 3 紧接着 0. A 变为 分别为 (0,3,1,2).
- 4th 查询:删除之间的元素 2 和 3,即 1,并输出移除值的总和,即 1. A 变为 分别为 (0,3,2).
- 5第查询:插入 5 紧接着 2. A 变为 分别为 (0,3,2,5).
- 6th 查询:删除之间的元素 0 和 5,即 3,2,并输出移除值的总和,即 5. A 变为 分别为 (0,5).
示例输入 2
2 1 0 2 0 1
示例输出 2
0
在 2nd 查询,我们删除之间的所有元素 0 和 1,但实际上不存在这样的元素,因此没有元素被删除,输出值为 0.
示例输入 3
10 1 0 1 1 2 0 2 2 0 2 1 0 1 5 2 0 5 2 2 6 1 6 1 9
示例输出 3
1 0 0 0