题意整理 有 n 个房间，每个房间有维护费用 c i c i ​ 和容量 p i p i ​ 。

有 m 个订单，每个订单有租金 v i v i ​ 和人数 d i d i ​ 。

每个订单必须安排在一个房间，且人数 d i ≤ d i ​ ≤ 房间容量 p j p j ​ 。

不同订单不能安排在同一房间。

最多选 o 个订单。

收益 = 所选订单的租金和 − 所选房间的维护费和。

目标是最大化收益。

数据范围与特殊条件 n , m ≤ 500 , 000 n,m≤500,000

o ≤ min ⁡ ( n , m ) o≤min(n,m)

特殊条件：若 p i < p j p i ​

这个特殊条件意味着：房间按容量排序后，维护费用是非递减的。 这很重要，它保证了容量大的房间费用不会比容量小的房间费用低，避免了一些复杂情况。

思路分析

1. 问题转化 我们要选择最多 o o 个订单，每个订单匹配一个不同的房间，且满足容量限制，最大化：

总收益

∑ 匹配 ( i , j ) ( v i − c j ) 总收益= 匹配(i,j) ∑ ​ (v i ​ −c j ​ ) 其中 d i ≤ p j d i ​ ≤p j ​ 。

2. 匹配的贪心想法 如果我们固定选哪些订单，那么给每个订单分配房间时，为了最大化收益，应该尽量选择维护费用 c j c j ​ 小的房间，同时满足容量限制。

反过来考虑： 对于每个订单，能容纳它的房间是 p j ≥ d i p j ​ ≥d i ​ 的房间。在这些房间中，我们应选择 c j c j ​ 最小的房间，这样 v i − c j v i ​ −c j ​ 最大。

3. 利用特殊条件排序 由于 p p 增大时 c c 不减，我们可以把房间按 p p 升序排序（这样 c c 也是升序或相等）。 把订单按 d d 升序排序。

这样，对于订单 i i，能容纳它的房间是 p j ≥ d i p j ​ ≥d i ​ 的那一段后缀。 因为 p p 和 c c 都单调不降，所以能容纳订单 i i 的房间中，费用最小的就是 第一个 p j ≥ d i p j ​ ≥d i ​ 的房间。

4. 贪心匹配流程 房间按 p p 升序排序。

订单按 d d 升序排序。

用双指针或优先队列进行匹配：

维护一个房间指针 p t r ptr 从最小的 p p 开始。

对于每个订单 i i，将 p j ≥ d i p j ​ ≥d i ​ 的所有房间加入一个按 c j c j ​ 排序的最小堆（但这里其实不需要堆，因为费用随 p p 增大不减，所以第一个满足的房间就是费用最小的）。

实际上更简单：因为房间按 p p 排序后，对于订单 i i，第一个满足 p j ≥ d i p j ​ ≥d i ​ 的房间就是费用最小的可用房间。

匹配后标记该房间已用，指针后移。

但这里有个问题：如果多个订单匹配同一个房间，只能用一个。 所以我们要在匹配时，选择收益 v i − c j v i ​ −c j ​ 最大的 o o 个匹配。

5. 最终算法框架 房间按 p p 升序排序。

订单按 d d 升序排序。

用双指针扫描：

房间指针 j j 从 0 开始。

对于每个订单 i i，找到第一个 p j ≥ d i p j ​ ≥d i ​ 的房间（因为排序后 p p 递增，所以 j j 只会往后移）。

计算这个匹配的收益 v i − c j v i ​ −c j ​ ，加入最大堆（按收益从大到小）。

从堆中取出收益最大的 o o 个匹配，求和即为答案。

但这样可能重复使用房间吗？ 会的，因为不同订单可能匹配到同一个房间（在指针 j j 不后移的情况下）。 题目要求不同订单不能在同一房间，所以一旦某个房间被匹配，就要排除它。

6. 正确贪心+数据结构 更精确的做法：

房间按 p p 升序。

订单按 d d 升序。

维护一个可用房间的集合（按 c c 排序的最小堆），初始为空。

双指针：

j

0 j=0

对每个订单 i i：

把所有 p j ≥ d i p j ​ ≥d i ​ 的房间加入堆（堆里按 c c 排序）。

从堆顶取出 c c 最小的房间，计算收益 v i − c v i ​ −c，将这个收益加入另一个最大堆（候选匹配堆）。

注意：这个房间已经用了，要从可用堆移除。

最后从候选匹配堆取前 o o 个正收益的匹配求和。

但这里有个问题：一个房间可能被多个订单考虑，但只能匹配一个订单。 所以应该在匹配时立即移除该房间。

7. 最终可行算法（参考已知解法） 实际上这类问题常用 贪心 + 并查集 或 贪心 + 平衡树 来避免重复使用房间。 但这里有一个已知简洁解法：

房间按 p p 升序排序。

订单按 d d 升序排序。

用一个小根堆存 ( c j , p j ) (c j ​ ,p j ​ )，按 c c 排序。

双指针 j

0 j=0，对每个订单 i i：

把所有 p j ≥ d i p j ​ ≥d i ​ 的房间加入堆。

如果堆不空，取出堆顶（ c c 最小），计算 v i − c v i ​ −c，加入结果候选的最大堆。

最后从候选的最大堆取前 o o 个正收益求和。

但这样还是可能重复用房间，因为取出的房间没有标记已用。 因此需要在取出堆顶后不再放回。