CF1458C 题解

题意

传送门

\(T\) 组测试数据，每次给一个 \(n\times n\) 的矩阵，每行每列都是个 \(1\to n\) 的排列。有 \(m\) 次操作，如果是 UDLR 就是要把整个矩阵每行/每列往一个方向循环移动一格。如果是 IC，就是把矩阵每行/每列变成原来的逆排列。求最后的矩阵。

数据范围：\(1\le T\le 1000\)，\(1\le \sum n\le 1000\)，\(1\le \sum m\le 10^5\)，\(1\le a_{i,j}\le n\)。

题解

最近的思维质量真是不行啊……看完题解觉得很简单，但为什么想不到呢……

首先如果没有 IC 是很简单的，维护位移即可。接着思考包含 IC 的一些简单情况。

如果只有 LRI，也就是单独考虑每行。如果第 \(i\) 位为 \(a_i\)，R 后第 \(i+1\) 位为 \(a_i\)，I 后第 \(a_i\) 位为 \(i\)。发现我们可以用一个二元组 \((i,a_i)\) 表示这个过程，即给一元加减，和交换两元。容易发现对于任意初始值，操作是一样的。于是可以保证复杂度。

于是答案就显而易见了：用三元组 \((i,j,a_{i,j})\)，每次操作都是给一元加减或交换两元。正确性易证。