問題一覧 > 通常問題

No.3094 Stapler

レベル : / AI推定難易度 : 1750 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 47
作問者 : RiRinbaru / テスター : hamo21 autumn09 downer ygussany
お気に入りにしたユーザー ProblemId : 12037 / 自分の提出
問題文最終更新日: 2025-04-06 16:46:26
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
QUPC2024 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。