[AGC006E] Rotate 3x3 题解

题意：

有一个 \(3\) 行 \(N\) 列的初始矩阵，\((i,j)\) 位置的数为 \(i+3\times j-3\)。

然后有一个这样的操作：选择一个 \(3 \times 3\) 的子矩阵，将这个子矩阵旋转 \(180°\)（具体见下面的图）。

现在给出一个 \(3\) 行 \(N\) 列的矩阵（矩阵中的数各不相同）

问能否通过若干次上述操作将初始矩阵变为给定的矩阵。

输入格式：

第一行给出 \(n\) ，然后三行共 \(3 \times n\) 个数表示初始矩阵。

输出格式：

一行，答案。

数据范围：

\(1\le n \le 10^5,~1 \le a_{i,j} \le 3n\) 。

看题解区好多 \(\mathcal{O}(n)\) 的神仙解法，我来讲一讲好理解的 \(\mathcal{O}(n \log n)\) 解法吧。

首先判掉明显不对的情况，这样每一行就可以看作一个数，并且有正负之分

注意到一次旋转只会交换奇偶性相同的相邻两列，即 \(i\) 和 \(i+2\) 。

那么不考虑正负的问题，把奇数列和偶数列分别换到正确的位置，操作数就是他们各自的逆序对数。

然后因为给了最终结果，所以正负是已知的，而且我们做的每个操作都是必须的。

那么一次奇数列的翻转会改变偶数列的一列的奇偶，偶数列也是一样的。

于是我们只需要判断一下「奇/偶数的操作数的奇偶性」和「偶/奇数的负数列的个数的奇偶性」就好了

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n, ans[2], sgn[N], tr[2][N], a[5][N], b[2][N];
int lowbit(int x) { return x & (-x); }
void add(int x, int c, int v = 1) { for(int i = x; i <= n; i += lowbit(i)) tr[c][i] += v; }
int qry(int x, int c, int r = 0) { for(int i = x; i; i -= lowbit(i)) r += tr[c][i]; return r; }
void fail() { cout << "No" << '\n'; exit(0); }
int pd(int x) { return (x + 2) / 3; }
void solve(int x, int odd)
{
    const int A = a[1][x], B = a[2][x], C = a[3][x];
    if(pd(A) != pd(B) || pd(A) != pd(C) || pd(B) != pd(C) || (pd(A) & 1) != odd) fail();
    if(A < B && B < C) { b[odd][++b[odd][0]] = (A + 5) / 6; return; }
    if(A > B && B > C) { b[odd][++b[odd][0]] = (A + 5) / 6; ++sgn[odd]; return; }
    return fail();
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= n; j++) cin >> a[i][j];
    for(int j = 1; j <= n; j++) solve(j, j & 1);
    for(int i = b[0][0]; i; i--) { ans[0] += qry(b[0][i], 0); add(b[0][i], 0); }
    for(int i = b[1][0]; i; i--) { ans[1] += qry(b[1][i], 1); add(b[1][i], 1); }
    if((ans[0] & 1) ^ (sgn[1] & 1)) fail();
    if((ans[1] & 1) ^ (sgn[0] & 1)) fail();
    cout << "Yes" << '\n';
    return 0;
}