No.1558 Derby Live
Problem Statement
A race among $N$ horses, numbered horse $1,2,\dots,N$, is about to be held.
The race follows the format below.
- The $N$ horses run through sections $1$ to $M$ in order.
- Each horse repeats: enter section $i$ $\rightarrow$ exit section $i$ $\rightarrow$ enter section $i+1$ $\rightarrow$ exit section $i+1$ $\dots$
- Since the sections are contiguous, you may assume that the rankings do not change between exiting section $i$ and entering section $i+1$.
- No $2$ horses are tied at the moment of entering or exiting any section.
- The horses enter section $1$ in the order horse $1,2,\dots,N$.
- Within each section, the rankings of the $N$ horses may change.
Here, for any $l,r$ with $1\le l\le r\le M$, the "excitement of the race" $E_{l,r}$ is defined as follows.
After the race starts, $Q$ queries arrive to you in order. There are $3$ types of queries, described below.
Process each query based on the information from the queries before it. (See also the constraints and samples for details.)
- type $1$ : You receive the information that the horse that entered section $D$ in the $i$-th place exited section $D$ in the $P_i$-th place. Ignore any information about section $D$ from before this query.
- type $2$ : Print all the horses that exited section $S$, in order starting from the $1$-st place.
- type $3$ : Print the "excitement of the race" $E_{L,R}$ from section $L$ to section $R$.
Constraints
Input
$N\ M\ Q$ $Query_1$ $\vdots$ $Query_Q$
$Query_i$ is one of the following $3$ forms.
$1\ D\ P_1 \dots P_N$
$2\ S$
$3\ L\ R$
Output
For each query of type $2$, print the numbers of the horses from $1$-st place to $N$-th place on one line, separated by spaces, followed by a newline.
For each query of type $3$, print $E_{L,R}$ on one line, followed by a newline.
Sample
Sample 1
Input
3 3 7 1 1 1 3 2 1 2 2 1 3 1 3 2 3 1 2 3 3 1 3 1 2 1 2 3 2 3
Output
2 3 1 4 2 1 3
After processing up to the $3$-rd query,
the order of the horses exiting section $1$ is $1,3,2$,
the order of the horses exiting section $2$ is $3,1,2$, and
the order of the horses exiting section $3$ is $2,3,1$.
Therefore, the $4$-th query prints 2 3 1.
Also, at the moment of exiting section $3$, horses $1,2,3$ are in $3$-rd, $1$-st, and $2$-nd place, respectively.
Therefore, noting that the order of the horses entering section $1$ is $1,2,3$, the $5$-th query prints
$E_{1,3}= |1-3|+|2-1|+|3-2|=4$.
After processing up to the $6$-th query,
the order of the horses exiting section $1$ is $1,3,2$,
the order of the horses exiting section $2$ is $1,3,2$, and
the order of the horses exiting section $3$ is $2,1,3$.
Therefore, the $7$-th query prints 2 1 3.
Sample 2
Input
4 5 10 1 1 3 4 2 1 1 2 1 3 2 4 2 2 1 3 2 3 4 1 3 1 3 1 2 1 2 3 4 1 4 2 1 4 3 2 4 1 5 3 2 4 1 3 1 5
Output
4 1 3 2 6 4 2 1 3 6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2
nok0
magsta