自动搬运

查看原文

来自洛谷，原作者为

	Wuyanru NOI2025 rp++ 喵~ | 不拿10级勾不改签名 | 我猜我是没机会改签名了

搬运于2025-08-24 22:54:18，当前版本为作者最后更新于2024-01-21 22:46:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道神秘的数据结构题。

题目链接。

题意

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

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

时限 $8s$。

$1\le n,q\le 3000$。

题解

发现时限非常大，而 $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$，常数确实大。

代码

感谢观看！