[SNOI2024] 矩阵

· · 题解

一道神秘的数据结构题。

题目链接。

题意

给定一个 n\times n 的矩阵，共有 q 次操作，分为两种：

  1. 给定一个正方形区域，将其逆时针旋转；
  2. 给定一个矩形区域，同时加一个值。

时限 8s。

## 题解 发现时限非常大，而 $n\times q$ 却只有 $9\times 10^6$。 普通的思路是，拿两棵平衡树分别维护矩阵的行与列。 矩阵加直接做，旋转可以把平衡树裂开，打反转标记，然后和另一棵平衡树合并在一起（横向的合并去竖向的，竖向的合并去横向的）。 时间复杂度是 $O(n^2+nq\log n)$，看起来很对？ 经过一些了解，在考场上这么写的人，大部分在本地跑到了 $100s\sim 250s$（包括我）。 下面是正解： 经过上面平衡树的尝试，我们完全可以知道，这道题维护的复杂度常数一定是巨大的。 这也就告诉我们，正解大概率是单次询问 $O(n)$ 的做法。 发现一个问题，假如只有矩阵加操作，这道题是好做的。 那么说明这道题的难点应该在于旋转操作。 考虑这么一件事情，如果保证旋转操作的对象一直是整个矩阵，这道题好做吗？ 非常好做，我们只需要额外维护，整个矩阵现在被操作了几次就好了。 为什么只需要这样就可以维护整个矩阵呢？ 因为在旋转的过程中，矩阵内部的“结构”是相对不变的，原来相邻的两个位置现在还是相邻。 这就是旋转操作的特点，回到原题，这告诉我们，假如去维护元素之间的相对位置，那么每一次旋转操作只有 $O(n)$ 个地方会被改变。 那么什么数据结构维护了一个矩阵中，元素之间的相对位置呢？答案是十字链表。 好，现在我们已经知道了旋转操作可以使用十字链表进行维护，那么矩阵加操作也很简单了。 单次 $O(1)$ 的矩阵加操作是困难的，但是单次 $O(n)$ 是简单的，我们只需要维护元素相对位置的同时，维护一下他们两个的差就好了。 做法总结： 1. 使用十字链表维护，每一个元素周围四个位置是谁，他们的差是多少； 2. 对于旋转操作，暴力找到需要断开的位置，然后旋转，再拼上，单次复杂度 $O(n)$； 3. 对于矩阵加操作，差变化的位置也只有 $O(n)$ 个，暴力找到位置，修改，单次复杂度 $O(n)$。 下面是几个实现细节： 1. 对于两种操作，都有 $O(n)$ 个位置需要修改，而链表不支持随机访问，复杂度为什么还是 $O(n)$ 的？ 可以发现，每一次需要修改的地方，一定是 $8$ 条（或者 $4$ 条）连续的线段，这些位置我们可以在 $O(n)$ 的时间内一起找到。 2. 假如我们维护每一个位置，左右上下分别是哪些元素，那么在一次旋转过后，他们的方向会改变，这怎么维护？ 这是一个好问题，我暂时没有想到很好的解决方案。 我的代码只是维护了四个位置的相对顺序，并没有强制钦定哪一个位置对应哪一个方向，访问的时候我们其实可以直接算出这个元素被旋转了几次。 总复杂度 $O(n^2+nq)$。 ## 代码 跑了 $7s$，常数确实大。 [代码](https://www.luogu.com.cn/paste/dt9gm6bc) 感谢观看！