No.3167 [Cherry 7th Tune C] Cut in Queue
タグ : / 解いたユーザー数 42
作問者 : 👑
Kazun
/ テスター :
👑 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$.
- 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.
- Type I
- 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もしくは右上の雲マークをクリックしてアカウントを作成してください。