F - Erase between X and Y Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

数列 A があります。 はじめ、A=(0) です。 （すなわち、A は 0 を唯一の要素として含む長さ 1 の数列です）。

クエリが Q 個与えられるので、順に処理してください。 i 番目 (1\leq i\leq Q) のクエリは以下のいずれかの形式です。

  • 1 x：A の中で x が現れる場所の直後に i を挿入する。
    • 具体的には、現在の A の j 番目の要素を A_j、A の長さを n としたとき、A_p=x なる p に対して 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、A の長さを n としたとき、A_p=x,A_q=y なる p,q に対して、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 の中である値が現れる場所は（存在するならば）一意であることに注意してください。

制約

  • 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

出力

2 種類目のクエリの個数を q 個として、q 行出力せよ。 i 行目には、2 種類目のクエリのうち i 番目のものにおいて出力すべき値を出力せよ。

入力例 1

6
1 0
1 1
1 0
2 2 3
1 2
2 0 5

出力例 1

1
5

最初、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
1 0
2 0 1

出力例 2

0

2 番目のクエリでは 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

Score : 525 points

Problem Statement

There is a sequence A. Initially, A=(0). (That is, A is a sequence of length 1 containing 0 as its only element).

You are given Q queries to process in order. The i-th query (1\leq i\leq Q) has one of the following forms:

  • 1 x: Insert i immediately after the location where x appears in A. Specifically, let A_j be the j-th element of the current A and n be the length of A. For p such that A_p=x, update A to (A_1,\dots,A_p,i,A_{p+1},\dots,A_n). It is guaranteed that A contains x immediately before processing this query.
  • 2 x y: Remove all elements between x and y in A, and output the sum of the values of the removed elements. Specifically, let A_j be the j-th element of the current A and n be the length of A. For p and q such that A_p=x and A_q=y, output A_{\min(p,q)+1} + \dots + A_{\max(p,q)-1} and update A to (A_1,\dots,A_{\min(p,q)},A_{\max(p,q)},\dots,A_n). It is guaranteed that A contains both x and y immediately before processing this query.

Note that for any sequence of queries, the same value never appears multiple times in A during the process of handling queries, and thus the position where a value appears in A is unique (if it exists).

Constraints

  • 1\leq Q \leq 5\times 10^5
  • For the i-th query:
    • If it is a type 1 query:
      • 0\leq x < i
      • A contains x immediately before processing the query.
    • If it is a type 2 query:
      • 0\leq x < y < i
      • A contains both x and y immediately before processing the query.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

Q
\text{query}_{1}
\text{query}_{2}
\vdots
\text{query}_{Q}

Here, \text{query}_{i} represents the i-th query and is given in one of the following forms:

1 x

2 x y

Output

Let q be the number of type 2 queries. Output q lines. The i-th line should contain the value to be output for the i-th type 2 query.

Sample Input 1

6
1 0
1 1
1 0
2 2 3
1 2
2 0 5

Sample Output 1

1
5

Initially, A=(0).

  • 1st query: Insert 1 immediately after 0. A becomes (0,1).
  • 2nd query: Insert 2 immediately after 1. A becomes (0,1,2).
  • 3rd query: Insert 3 immediately after 0. A becomes (0,3,1,2).
  • 4th query: Remove the elements between 2 and 3, namely 1, and output the sum of the removed values, which is 1. A becomes (0,3,2).
  • 5th query: Insert 5 immediately after 2. A becomes (0,3,2,5).
  • 6th query: Remove the elements between 0 and 5, namely 3,2, and output the sum of the removed values, which is 5. A becomes (0,5).

Sample Input 2

2
1 0
2 0 1

Sample Output 2

0

In the 2nd query, we remove all elements between 0 and 1, but there are actually no such elements, so no elements are removed and the output value is 0.

Sample Input 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

Sample Output 3

1
0
0
0