← 返回题目列表

AtCoder · abc421_f

I. 在 X 和 Y 之间擦除

中文机器翻译题面 查看原题

分数: 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 在处理查询之前。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

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