2025.5.25 作业 - # ABC459C Drop Blocks

题目描述

有 \(N\) 个格子排成一横排，初始所有格子都没有堆放方块。
给出 \(Q\) 次询问，按顺序处理，询问分为两种：

1. 1 x：在从左往右第 \(x\) 个格子上放1个方块。放完后，如果所有格子都至少有1个方块，则每个格子全部拿掉1个方块。
2. 2 y：输出方块数量 ≥ y 的格子一共有多少个。

输入格式

第一行 \(N\ Q\)，之后 \(Q\) 行每行一条询问：

• 1 x
• 2 y

输出格式

对于每条类型2询问，各输出一行答案。

样例输入1

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

样例输出1

2
1
1

样例说明

\(N=3\)，初始三个格子方块数量：\((0,0,0)\)

1. 操作1 1：1号格子+1 → \((1,0,0)\)，存在空格，不用全减1。
2. 操作1 3：3号格子+1 → \((1,0,1)\)。
3. 操作1 3：3号格子+1 → \((1,0,2)\)。
4. 操作2 1：方块≥1的格子有1、3，共2个 → 输出2。
5. 操作2 2：方块≥2的只有3号，共1个 → 输出1。
6. 操作1 2：2号+1 → \((1,1,2)\)；现在全部格子都≥1，所有格子统一减1 → \((0,0,1)\)。
7. 操作2 1：方块≥1的只有3号，共1个 → 输出1。

数据范围

• \(1\le N,Q \le 3\times10^5\)
• \(1\le x\le N,\ 1\le y\le3\times10^5\)
• 至少存在一次2类询问。

---

简要解题思路

桶思想 + 前缀和

• cnt[k]: 第 k 根柱子当前的积木数
• s[i]: 有多少根柱子至少有 i 个积木
• m: 当前所有柱子都达到的最小高度

核心公式

当 x==1 (放置积木到柱子k):cnt[k]++                          // 柱子k高度+1s[cnt[k]]++                       // 高度分布更新当 x==2 (查询):答案 = s[k + m]                   // 至少有 k+m 个积木的柱子数

• 参考代码

#include <iostream>
using namespace std;
int n,q,cnt[300003],sum,m,s[600003];
int main() {cin>>n>>q;while (q--) {int x,k;cin>>x>>k;if (x==1) {cnt[k]++; s[cnt[k]]++;if (s[m+1]==n) m++;}else {cout<<s[k+m]<<endl;}}return 0;
}