CF198E

· · 题解

三年前见到这题的时候完全不会，看题解都看不明白。现在看这题觉得非常简单啊。不过现在的我跟三年前的我比起来，只是多会了几个数据结构和常见套路而已吧，就连思维都僵化了。

不说多了，讲下这题咋做。

由于船是固定的，那么每个机械臂需要的距离都是固定的，不妨设为 d_i。

假如我们现在有个机械臂力量为 p，长度为 r，那么它可以拿起第 i 个机械臂，当且仅当 d_i\leq r 且 m_i\leq p。假如第 i 个机械臂能拿到第 j 个机械臂，那么就连一条 i\to j 的有向边，然后从起始的机械臂 BFS 一遍就可以得到所有能拿到的机械臂。

这样做是 O(n^2) 的。这个 BFS 做法并不需要建边，假设当前 BFS 到了 x，那么只要枚举所有现在还没有被拿到的机械臂 y 判断一下 x 是否能拿到 y 就行。现在只需要优化找这个 y 的过程。

考虑一个套路：每次都找到一个 y，并将这个 y 删除，一直到没有符合要求的 y 才停止。

容易发现判断条件是一个二维偏序的形式。由于机械臂的排列顺序不会影响答案，那么不妨先将机械臂按照 d_i 从小到大排序，那么满足 d_i\leq r 的机械臂就是一段前缀区间，这样就可以利用线段树解决了。

然后就是要满足第二个 m_i\leq p 的条件。由于 y 的取出顺序也不会影响答案，那么只需要每次取出区间中 m_i 最小的机械臂就行了。于是这个线段树只需要维护区间最小值。

不过我的做法是对线段树上每个节点对区间内的所有机械臂维护一个 m_i 单调不增的栈，记录机械臂的编号。查询到一个节点上时，如果栈顶已经被拿过了就弹出。如果当前栈顶的 m_i 满足条件就取它，否则这个区间内的机械臂都拿不走。

code