C - Snake Queue Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

ヘビの待ち行列があります。最初、列は空です。

クエリが Q 個与えられるので、与えられた順に処理してください。クエリは以下の 3 種類です。

  • タイプ 1 : 1 l の形式で与えられる。長さ l のヘビが列の末尾に追加される。このとき追加するヘビの頭の位置は、元の列が空の場合は座標 0、そうでない場合は最後尾のヘビの頭の座標に最後尾のヘビの長さを加えた座標となる。
  • タイプ 2 : 2 の形式で与えられる。列の先頭にいるヘビが列から抜ける。このとき、列が空でないことは保証される。抜けたヘビの長さを m として、列に残っている全てのヘビの頭の座標が m だけ減少する。
  • タイプ 3 : 3 k の形式で与えられる。列の先頭から数えて k 番目にいるヘビの頭の座標を出力せよ。このとき、列には少なくとも k 匹のヘビがいることが保証される。

制約

  • 1 \leq Q \leq 3 \times 10^{5}
  • タイプ 1 のクエリにおいて、1 \leq l \leq 10^{9}
  • タイプ 2 のクエリにおいて、列が空でないことが保証される
  • タイプ 3 のクエリにおいて、列にいるヘビの数を n として、1 \leq k \leq n
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

ただし、\text{query}_i は i 個目のクエリを表し、以下のいずれかの形式である。

1 l

2

3 k

出力

タイプ 3 のクエリの個数を q として、q 行出力せよ。i 行目には、i 個目のタイプ 3 のクエリに対する答えを出力せよ。

入力例 1

7
1 5
1 7
3 2
1 3
1 4
2
3 3

出力例 1

5
10
  • 1 個目のクエリ : 長さ 5 のヘビが列に追加される。列にヘビはいないため、追加されたヘビの頭の座標は 0 となる。
  • 2 個目のクエリ : 長さ 7 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 0 で長さが 5 のため、追加されたヘビの頭の座標は 5 となる。
  • 3 個目のクエリ : 前から 2 番目にいるヘビの頭の座標を出力する。列にいるヘビの頭の座標は前から順に 0, 5 であるため、5 を出力する。
  • 4 個目のクエリ : 長さ 3 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 5 で長さが 7 のため、追加されたヘビの頭の座標は 12 となる。
  • 5 個目のクエリ : 長さ 4 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 12 で長さが 3 のため、追加されたヘビの頭の座標は 15 となる。
  • 6 個目のクエリ : 先頭のヘビが列から抜ける。抜けたヘビの長さが 5 であるため、列にいるヘビの頭の座標は 5 だけ減少する。列に残っているヘビの頭の座標は先頭から順に 0,7,10 となる。
  • 7 個目のクエリ : 前から 3 番目にいるヘビの頭の座標を出力する。列にいるヘビの頭の座標は前から順に 0, 7, 10 であるため、10 を出力する。

入力例 2

3
1 1
2
1 3

出力例 2




タイプ 3 のクエリが 1 つもない場合もあります。













入力例 3
10
1 15
1 10
1 5
2
1 5
1 10
1 15
2
3 4
3 2













出力例 3
20
5







Score : 300 points







Problem Statement
There is a queue of snakes. Initially, the queue is empty.


You are given Q queries, which should be processed in the order they are given. There are three types of queries:


    

  • Type 1: Given in the form 1 l. A snake of length l is added to the end of the queue. If the queue was empty before adding, the head position of the newly added snake is 0; otherwise, it is the sum of the head coordinate of the last snake in the queue and the last snake’s length.
    • 

  • Type 2: Given in the form 2. The snake at the front of the queue leaves the queue. It is guaranteed that the queue is not empty at this time. Let m be the length of the snake that left, then the head coordinate of every snake remaining in the queue decreases by m.
    • 

  • Type 3: Given in the form 3 k. Output the head coordinate of the snake that is k-th from the front of the queue. It is guaranteed that there are at least k snakes in the queue at this time.
    • 












Constraints
    

  • 1 \leq Q \leq 3 \times 10^{5}
    • 

  • For a query of type 1, 1 \leq l \leq 10^{9}
    • 

  • For a query of type 2, it is guaranteed that the queue is not empty.
    • 

  • For a query of type 3, let n be the number of snakes in the queue, then 1 \leq k \leq n. 
    • 

  • 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 is the i-th query in one of the following forms:


1 l




2




3 k













Output
Let q be the number of queries of type 3. Print q lines. The i-th line should contain the answer to the i-th type 3 query.















Sample Input 1
7
1 5
1 7
3 2
1 3
1 4
2
3 3













Sample Output 1
5
10




    

  • 1st query: A snake of length 5 is added to the queue. Since the queue was empty, the head coordinate of this snake is 0.  
    • 

  • 2nd query: A snake of length 7 is added to the queue. Before adding, the last snake has head coordinate 0 and length 5, so the newly added snake’s head coordinate is 5.  
    • 

  • 3rd query: Output the head coordinate of the snake that is 2nd from the front. Currently, the head coordinates of the snakes in order are 0, 5, so output 5.  
    • 

  • 4th query: A snake of length 3 is added to the queue. Before adding, the last snake has head coordinate 5 and length 7, so the new snake’s head coordinate is 12.  
    • 

  • 5th query: A snake of length 4 is added to the queue. Before adding, the last snake has head coordinate 12 and length 3, so the new snake’s head coordinate is 15.  
    • 

  • 6th query: The snake at the front leaves the queue. The length of the snake that left is 5, so the head coordinate of each remaining snake decreases by 5. The remaining snake’s head coordinate becomes 0, 7, 10.  
    • 

  • 7th query: Output the head coordinate of the snake that is 3rd from the front. Currently, the head coordinates of the snakes in order are 0, 7, 10, so output 10.
    • 














Sample Input 2
3
1 1
2
1 3













Sample Output 2



It is possible that there are no queries of type 3.













Sample Input 3
10
1 15
1 10
1 5
2
1 5
1 10
1 15
2
3 4
3 2













Sample Output 3
20
5