C - Drop Blocks 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

N 個のマスが左右一列に並んでいます。 はじめ、すべてのマスには何も置かれていません。

Q 個のクエリが与えられるので、順に処理してください。 各クエリは次の 2 種類のいずれかです。

  • 1 x : 左から x 番目のマスにブロックを 1 個積む。その後、すべてのマスに 1 個以上のブロックが積まれているならば、すべてのマスからブロックを 1 個ずつ取り除く。
  • 2 y : y 個以上のブロックが積まれているマスの個数を出力する。

制約

  • 1\leq N\leq 3\times 10^5
  • 1\leq Q\leq 3\times 10^5
  • 1\leq x\leq N
  • 1\leq y\leq 3\times 10^5
  • 入力はすべて整数
  • 2 種類目のクエリが少なくとも 1 つ存在する。

入力

入力は以下の形式で標準入力から与えられる。

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリ \mathrm{query}_i (1\leq i\leq Q) は次の形式のいずれかで与えられる。

1 x

2 y

出力

2 種類目のクエリの個数を K 個として、K 行出力せよ。i 行目 (1\leq i\leq K) には i 番目の 2 種類目のクエリに対する答えを出力せよ。

入力例 1

3 7
1 1
1 3
1 3
2 1
2 2
1 2
2 1

出力例 1

2
1
1

N=3 であり、はじめ、左から 1,2,3 番目に積まれているブロックの数は (0,0,0) です。
クエリは順に次のように処理されます。

  • 左から 1 番目のマスに 1 個ブロックを積みます。ブロックの積まれていないマスが存在するため、それ以上の操作は行いません。左から 1,2,3 番目に積まれているブロックの数は (1,0,0) となります。
  • 左から 3 番目のマスに 1 個ブロックを積みます。左から 1,2,3 番目に積まれているブロックの数は (1,0,1) となります。
  • 左から 3 番目のマスに 1 個ブロックを積みます。左から 1,2,3 番目に積まれているブロックの数は (1,0,2) となります。
  • 1 個以上のブロックが積まれているマスは左から 1 番目と 3 番目のマスの 2 つです。よって、2 を出力します。
  • 2 個以上のブロックが積まれているマスは左から 3 番目のマスの 1 つだけです。よって、1 を出力します。
  • 左から 2 番目のマスに 1 個ブロックを積みます。この時点ですべてのマスにブロックが 1 個以上積まれているため、すべてのマスからブロックを 1 個取り除きます。左から 1,2,3 番目に積まれているブロックの数は (0,0,1) となります。
  • 1 個以上のブロックが積まれているマスは左から 3 番目のマスの 1 つだけです。よって、1 を出力します。

よって、2,1,1 をこの順に各行に出力します。

Score : 300 points

Problem Statement

There are N cells arranged in a row from left to right. Initially, no blocks are placed in any cell.

You are given Q queries, so process them in order. Each query is one of the following two types:

  • 1 x: Place 1 block in the x-th cell from the left. Then, if every cell has at least 1 block, remove 1 block from every cell.
  • 2 y: Output the number of cells that have at least y blocks.

Constraints

  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq Q \leq 3 \times 10^5
  • 1 \leq x \leq N
  • 1 \leq y \leq 3 \times 10^5
  • All input values are integers.
  • At least one query of the second type exists.

Input

The input is given from Standard Input in the following format:

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query \mathrm{query}_i (1 \leq i \leq Q) is given in one of the following formats:

1 x

2 y

Output

Let K be the number of queries of the second type. Output K lines. The i-th line (1 \leq i \leq K) should contain the answer to the i-th query of the second type.

Sample Input 1

3 7
1 1
1 3
1 3
2 1
2 2
1 2
2 1

Sample Output 1

2
1
1

N=3, and initially the numbers of blocks placed in the 1-st, 2-nd, 3-rd cells from the left are (0, 0, 0). The queries are processed in order as follows:

  • Place 1 block in the 1-st cell from the left. There exist cells with no blocks, so no further action is taken. The numbers of blocks in the 1-st, 2-nd, 3-rd cells become (1, 0, 0).
  • Place 1 block in the 3-rd cell from the left. The numbers of blocks in the 1-st, 2-nd, 3-rd cells become (1, 0, 1).
  • Place 1 block in the 3-rd cell from the left. The numbers of blocks in the 1-st, 2-nd, 3-rd cells become (1, 0, 2).
  • The cells with at least 1 block are the 1-st and 3-rd cells from the left, so there are 2 such cells. Thus, output 2.
  • The cells with at least 2 blocks is only the 3-rd cell from the left, so there is 1 such cell. Thus, output 1.
  • Place 1 block in the 2-nd cell from the left. At this point, every cell has at least 1 block, so 1 block is removed from every cell. The numbers of blocks in the 1-st, 2-nd, 3-rd cells become (0, 0, 1).
  • The cells with at least 1 block is only the 3-rd cell from the left, so there is 1 such cell. Thus, output 1.

Thus, output 2, 1, 1 in this order, one per line.