No.3094 Stapler
Problem Statement
There is a stack of $N$ sheets of paper. Using a stapler, you can join sheets that are adjacent in the stack. Joined sheets form a group, and they remain a group until all the staples used to join them are removed.
You are given $Q$ queries. Process each of them in order.
-
1 L R: Staple the sheets between the $L$-th sheet from the top and the $R$-th sheet from the top. -
2 q: Remove the staple used for stapling in the $q$-th query (it is guaranteed that the $q$-th query is a query $1$). -
3: Print the current number of groups of sheets.
Input
The input is given in the following format.
$N$
$Q$
$ \mathrm{query}_1 $
$ \mathrm{query}_2 $
$:$
$ \mathrm{query}_Q $
(15:47 The problem statement was corrected.)
- $1\leq N\leq 10^6$
- $1\leq Q\leq 10^5$
- All input values are integers.
For each query, the query type $c_i (=1, 2, 3)$ is given first. For query $1$, integers $L, R$ are additionally given, and for query $2$, an integer $q$ is additionally given.
That is, each query is given in one of the following $3$ formats.
(16:45 The problem statement was corrected.)
$1\ L\ R$
$2\ q$
$3$
(16:18 For query 1, $L\leq R$ holds.)
(16:41 For query 1, $1\leq L\leq R\leq N$ holds.)
Output
For each query 3, print the answer in order.
Print a newline at the end.
Sample
Sample 1
Input
7 9 1 3 5 1 2 4 3 1 5 7 3 2 1 3 2 4 3
Output
4 2 3 5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hamo21