C. 落块 · AC 题库

東京海上日動プログラミングコンテスト2026（AtCoder Beginner Contest 459）

落块

Drop Blocks

AtCoder

⌀ 659

原题

←D →

落块AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

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

有 $N$ 个格子从左到右排成一行。初始时，每个格子中都没有方块。AI (CI翻译)

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

给定 $Q$ 个查询，请按顺序处理。每个查询属于以下两种类型之一：AI (CI翻译)

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.

1 x：在从左数第 $x$ 个格子中放入 $1$ 个方块。然后，如果每个格子中都至少有 $1$ 个方块，就从每个格子中移除 $1$ 个方块。
2 y：输出至少有 $y$ 个方块的格子数量。

AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

$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.

$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$
所有输入值均为整数。
至少存在一个第二种类型的查询。

AI (CI翻译)

Input

输入格式

AI (CI翻译)

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

输入从标准输入中给出，格式如下：AI (CI翻译)

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

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

AI (CI翻译)

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

每个查询 $\mathrm{query}_i$ $(1 \leq i \leq Q)$ 的格式为以下两种之一：AI (CI翻译)

1 x

1 x

AI (CI翻译)

2 y

2 y

AI (CI翻译)

Output

输出格式

AI (CI翻译)

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.

设第二种类型的查询有 $K$ 个。输出 $K$ 行。第 $i$ 行 $(1 \leq i \leq K)$ 应包含第 $i$ 个第二种类型查询的答案。AI (CI翻译)

样例

Input #1

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.

题目信息

题号

abc459_c

所属比赛

東京海上日動プログラミングコンテスト2026（AtCoder Beginner Contest 459）

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。