# 搅拌机：行列索引与转置标记

Codex（GPT-6）：用行列排列表示当前矩阵，并给出顺时针旋转的更新规则及证明。程序为 [alternative.cpp](alternative.cpp)，与[直接维护矩阵](solution.zh.md)并列，支持完整数据。

## 表示与操作

保存初始矩阵 $G$ 、行索引数组 $R$ 、列索引数组 $S$ 和布尔标记 $b$ . 使用零起始下标；初始两数组都是自然排列，$b$ 为假。当前格子 $(i,j)$ 的值定义为

$$b=0:\quad G[R_i][S_j],\qquad b=1:\quad G[S_j][R_i]$$

交换当前两行，只交换 $R$ 的两个元素；交换两列，只交换 $S$ 的两个元素。参数合法性按当前数组长度判断。

旋转时将两数组交换，把新的列数组反转，再翻转 $b$ ：

$$R' = S,\qquad S' = \operatorname{reverse}(R),\qquad b'=1-b$$

这也同步交换了当前行数和列数。

## 正确性

初始表示直接对应 $G$ . 行或列索引的交换恰好交换对应整行或整列。对旋转，新格子 $(i,j)$ 应取自旧格子 $(n-1-j,i)$ . 若 $b=0$ ，它的值是 $G[R_{n-1-j}][S_i]$ ；更新后 $b'=1$ ，新表示给出同一个值。若 $b=1$ ，将两个坐标角色交换可得完全相同的结论。由归纳，表示始终等于真实操作后的矩阵。

## 代价

交换索引为 $O(1)$ ，旋转的数组反转为 $O(n+m)$ 上界，其中 $n,m$ 表示当前维数；额外索引空间为 $O(n+m)$ . 初始矩阵占 $O(nm)$ ，旋转无须第二份矩阵。尽管维护更轻，所有合法状态仍需输出。令 $C=nm$ 、$V$ 为合法操作数，总时间仍为 $O(C+K+VC)$ ，总空间仍为 $O(C)$ .

直接矩阵方案更接近题意，索引方案需要仔细区分转置状态下两数组的含义。复杂度结论包含打印开销，不以这项表示变化宣称整体数量级加速。