CF1458C Latin Square

题意

给出一个 $n\times n$ 的矩阵，每行每列都是一个 $[1, n]$ 的排列，有 $m$ 次操作

• U 表示整个矩阵循环下移一格
• D 表示整个矩阵循环上移一格
• L 表示整个矩阵循环左移一格
• R 表示整个矩阵循环右移一格
• I 表示把矩阵每一行变为原来排列的逆
• R 表示把矩阵每一列变为原来排列的逆

多组测试数据，$1\le T\le 1000$，$1\le n, m$，$\sum n\le 1000,\sum m\le 10^5$

题解

考虑排列逆的含义

一个排列 $a$ 可以表示为若干个点 $(i, a_i)$
根根据排列逆的定义，我们可以发现 $a$ 的逆 $a^{-1}$ 可以表示为若干个点 $(a_i, i)$，即交换 $xy$ 坐标

对于矩阵 $a$ 我们把它表示为若干个三维的点 $(i, j, a_{i, j})$
I 操作对应交换 $yz$ 坐标
C 操作对应交换 $xz$ 坐标

剩下的操作也很好办
U 操作对应所有 $x$ 坐标-1
D 操作对应所有 $x$ 坐标+1
L 操作对应所有 $y$ 坐标-1
R 操作对应所有 $y$ 坐标+1

维护各个坐标对应的初始时的坐标和各个坐标的变化量即可

总时间复杂度为 $\Theta(n^2+m)$

代码 codeforces submission 142751178