[Jisuanke-T54180] wy 的玩具规划

[Wizmann]

Description

Problem

有N个柜子，每个柜子可以放无限多的。有M个操作。操作分两种：

• 操作1：从第x到第y个柜子里各放上一个价值为v的物品
• 操作2：询问第x到第y个柜子里的所有物品中，价值第v高的物品的价值

求所有操作2的结果。

• n, m <= 50000
• 对于操作2，一定有解

Solution

整体二分模板题。

整体二分是一种离线二分搜索，同时在值域和询问上进行划分，从而减少在线二分搜索的重复操作。

整体二分可以解决这样的问题：

1. 询问的答案具有可二分性
2. 修改对判定答案的贡献互相独立，修改之间互不影响效果
3. 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值
4. 贡献满足交换律，结合律，具有可加性
5. 题目允许使用离线算法 ——许昊然《浅谈数据结构题几个非经典解法》

对于本题来说，上面的条件可以解释为：

1. 我们可以假设某一次查询的排名为k，结果为v。我们可以将大于等于v的所有值加入查询区间，观察区间内是否有大于等于k个数。
2. 向区间内的柜子放入物品的操作是独立的，无后效的（类比DP）
3. 修改对于结果的影响是确定的
4. 修改可以打乱顺序，明显符合交换律，结合律，可加性
5. 本题一定可以使用离线

整体二分的执行思路如下：

1. 二分枚举值域(l, r)，假设当前的结果为m = (l + r) / 2
2. 遍历所有的操作（包括添加与查询）
   • 对于添加操作：放入的物品价值为v，若v < m，将操作放入左子数组；若v >= m，将操作放入右子数组
   • 对于查询操作：检查当前结果m是否大于/小于最终结果（可二分性），若小于，将查询放入右子数组；若大于，放入左子数组
3. 分别递归处理左右子数组

对于检查结果的操作，本题使用了树状数组（区间修改，区间查询）。

Code

参考链接

• OI Wiki
• 相似题目：Luogu P2617 Dynamic Rankings