CF706E Working routine 题解

TangyixiaoQAQ · 2026-01-23 08:36:05 · 题解

题意简析

在一个 n \times m 的格点上，交换 q 次相同的点无交集的矩形，求最终结果。

思路解析

暴力

暴力的思路是很好想的，考虑每次交换时，先将其中一个矩形的所有点存到一个临时矩形中，再将另一个矩形覆盖到原来矩形上，最后将临时矩形转移到另一个矩形上，完成一次交换，时间复杂度 O(nmq)。

链表

考虑到我们每次交换时，并不需要交换其中的所有元素，类似于分块中块状链表的思想，我们可以把一行的很多数看成一个块，交换时直接交换这个块的首尾即可，如图所示：

既然你已经想到了用一维链表优化，那么为什么不能用二维呢？

类似于前面，我们再画一个图：

我们这里就可以发现，我们只需要交换矩形的上下左右四条边上的点的指针即可，时间复杂度 O((n+m)q)。