A7676 | Drop Blocks
时间限制2s
内存限制1024MB
通过 / 提交0/0
题目描述
有 $N$ 个单元格从左到右排成一行。初始时,所有单元格中均未放置任何方块。
给你 $Q$ 个查询,请按顺序处理它们。每个查询为以下两种类型之一:
*
*
给你 $Q$ 个查询,请按顺序处理它们。每个查询为以下两种类型之一:
*
1 x:在从左往右数第 $x$ 个单元格中放置 $1$ 个方块。然后,若每个单元格中都至少有 $1$ 个方块,则从每个单元格中移除 $1$ 个方块。*
2 y:输出至少含有 $y$ 个方块的单元格数量。输入格式
输入从标准输入中按以下格式给出:
> $N$ $Q$
> $\mathrm{query}_1$
> $\mathrm{query}_2$
> $\vdots$
> $\mathrm{query}_Q$
每个查询 $\mathrm{query}_i$($1 \leq i \leq Q$)以如下两种格式之一给出:
> $1$ $x$
> $2$ $y$
> $N$ $Q$
> $\mathrm{query}_1$
> $\mathrm{query}_2$
> $\vdots$
> $\mathrm{query}_Q$
每个查询 $\mathrm{query}_i$($1 \leq i \leq Q$)以如下两种格式之一给出:
> $1$ $x$
> $2$ $y$
输出格式
设 $K$ 为第二类查询的数量。输出 $K$ 行。第 $i$ 行($1 \leq i \leq K$)应包含第 $i$ 个第二类查询的答案。
输入输出样例
输入 #1
3 7 1 1 1 3 1 3 2 1 2 2 1 2 2 1
输出 #1
2 1 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$,每行一个。
### 约束条件
* $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$
* 所有输入值均为整数。
* 至少存在一个类型为二的查询。
$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$,每行一个。
### 约束条件
* $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$
* 所有输入值均为整数。
* 至少存在一个类型为二的查询。
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?