問題一覧 > 通常問題

No.3167 [Cherry 7th Tune C] Cut in Queue

レベル : / AI推定難易度 : 1725 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 42
作問者 : 👑 Kazun / テスター : 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 10218 / 自分の提出
問題文最終更新日: 2025-05-20 00:20:05
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 468 Desire for Approval ~Ash blown by the draft leads to the door to a new beginning~ (順位表) の他の問題:

Problem Visual

▶ Open to reveal the problem visual

Problem Statement

You are given a permutation $A$ of $(1, 2, \dots, N)$. There is also an integer sequence $B$ of length $Q$, and the $j$-th term $B_j$ of $B$ is $B_j = N + j$. That is, $$B = (N + 1, N + 2, \dots, N + Q)$$ .

For these $A, B$, perform the following $Q$ operations in order.

  • Type I: Given in the form 1 a. Let $b$ be the first term of $B$, and remove that first term from $B$. Then, depending on the value of $a$, do one of the following. It is guaranteed that $a$ is "$0$ or an integer that exists in $A$ at the time this query is given".
    • When $a = 0$: append $b$ to the end of $A$.
    • When $a \neq 0$: insert $b$ immediately before the term of $A$ that equals $a$.
    It can be proved that $B$ is not empty at the time this query is given.
  • Type II: Given in the form 2. Remove the first term from $A$. It is guaranteed that $A$ is not empty at the time this query is given.
  • Type III: Given in the form 3 k. Print the $k$-th term of $A$. For $k$, it is guaranteed that $1 \leq k \leq \lvert A \rvert$, where $\lvert A \rvert$ denotes the length of $A$ at the time this query is given.

Constraints

  • $1 \leq N \leq 3 \times 10^5$.
  • $A$ is a permutation of $(1, 2, \dots, N)$.
  • $1 \leq Q \leq 3 \times 10^5$.
  • Constraints for each query
    • Type I
      • $a$ is "$0$ or an integer that exists in $A$ at the time this query is given".
    • Type II
      • $A$ is not empty at the time this query is given.
    • Type III
      • $1 \leq k \leq \lvert A \rvert$, where $\lvert A \rvert$ denotes the length of $A$ at the time this query is given.
  • All input values are integers.
  • At least $1$ query of Type III is given.

Input

The input is given from Standard Input in the following format.
$N$
$A_1$ $A_2$ $\dots$ $A_N$
$Q$
${\rm Query}_1$
${\rm Query}_2$
$\vdots$
${\rm Query}_Q$
Each query ${\rm Query}_q$ is given in one of the following formats.
  • Type I
    $1$ $a$
  • Type II
    $2$
  • Type III
    $3$ $k$

Output

Suppose that, among the $Q$ queries, $Q_3$ queries are of Type III. Then, the output consists of $Q_3$ lines.

On the $r~(1 \leq r \leq Q_3)$-th line, print as an integer the answer to the $r$-th given Type III query.

Do not forget the newline at the end.

Sample

Sample 1
Input
5
3 5 2 4 1
7
1 2
1 0
2
3 5
2
1 6
3 1
Output
1
8

Initially, $A = (3,5,2,4,1), B = (6,7,8,9,10,11,12)$. Each query is processed as follows.

  • (Query 1) Remove $b = 6$, the first term of $B$, and in $A$, insert $b=6$ immediately before $a = 2$. After this query, $A = (3,5,6,2,4,1), B = (7,8,9,10,11,12)$.
  • (Query 2) Remove $b = 7$, the first term of $B$. For $A$, since $a = 0$, insert $b = 7$ at the end of $A$. After this query, $A = (3,5,6,2,4,1,7), B = (8,9,10,11,12)$.
  • (Query 3) Remove the first term of $A$. After this query, $A = (5,6,2,4,1,7), B = (8,9,10,11,12)$.
  • (Query 4) The $5$-th term of $A$ is $1$. Thus, print $1$.
  • (Query 5) Remove the first term of $A$. After this query, $A = (6,2,4,1,7), B = (8,9,10,11,12)$.
  • (Query 6) Remove $b = 8$, the first term of $B$, and in $A$, insert $b=8$ immediately before $a = 6$. After this query, $A = (8,6,2,4,1,7), B = (9,10,11,12)$.
  • (Query 7) The $1$-st term of $A$ is $8$. Thus, print $8$.

Sample 2
Input
1
1
9
2
1 0
3 1
2
1 0
3 1
2
1 0 
3 1
Output
2
3
4

A Type II query is never given when $A$ is empty, but $A$ itself may become empty.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。