[??记录]AT2166 [AGC006E] Rotate 3x3
command_block
2021-04-22 15:22:07
**题意** : 有一个 $3\times n$ 的矩阵，初始时，位置 $[i,j]$ 上的数字为 $i+3j-3$ ，下图是 $n=5$ 时的情况 ：
每次操作可以将一个 $3\times 3$ 的子矩阵旋转 $180\degree$ ，如下图 ：
给出矩阵的目标状态，判定是否能通过若干次上述操作达到。
$n\leq 10^5$ ，时限$\texttt{2s}$。
------------
- **性质** 每一列的三个数是不会分开的，但可能上下翻转。
于是，将三个数映射成一个数，且有正负之分，问题转化为 ：
给出长为 $n$ 的数组 $x_{1...n}$ ，与目标状态 $x'_{1...n}$ ，每次操作可以指定 $i$ 并交换 $x_{i-1},x_{i+1}$ ，并将 $x_{i-1},x_i,x_{i+1}$ 均乘以 $-1$。
若 $x'$ 中的元素不可能从 $x$ 中得来，则无解。
- **性质** 操作不能改变某个数所在位置的奇偶性
若一个数的起点和终点位置奇偶性不同，则无解。
- **性质** 操作是可逆的，且逆操作为操作本身
可以把问题转化为由 $x'$ 操作到 $x$。
先不考虑正负，问题相当于利用交换 $x_{i-1},x_{i+1}$ 将数组排序。
按照奇偶分为两个序列，分别冒泡排序即可。
计算出排好序后的正负，再尝试将全部负数修正为正数。
先考虑排好序后如何调整。
- 若奇位置或者偶位置的负数为奇数个，则必定无解。
因为奇位置和偶位置是已经有序的，要想结束时仍然有序，一定只能进行偶数次交换，故不可能影响奇数次正负性。
先消去所有在奇数位置的负数。
将负数两两配对，假设为 $a,b$。先将 $a$ 运到某个位置 $i$ ，操作 $x_{i-1},x_i,x_{i+1}$ 将其变号。再将 $b$ 运到 $i$ ，操作 $x_{i-1},x_i,x_{i+1}$ 将其变号。最后将两者运送回去。
运送 $x,y$ 产生的交换都和自己抵消，不会影响正负性和顺序，于是我们就这样消去了一对负数。
而对 $x_{i-1},x_i,x_{i+1}$ 的两次操作虽然会牵扯到偶数位置，但也抵消了。
故有解的充要条件是，奇位置或者偶位置的负数为偶数个。
对奇位置的交换操作会影响两个奇位置和一个偶位置，对奇位置的负数个数奇偶性无影响，而对偶位置的负数个数奇偶性有影响。
于是，计算出两者的逆序对数目（即为交换次数）即可，复杂度为 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 100500
using namespace std;
int n,t[MaxN];
#define lbit(x) (x&-x)
void add(int p)
{while(p<=n){t[p]++;p+=lbit(p);}}
int qry(int p){
int ret=0;
while(p){ret+=t[p];p^=lbit(p);}
return ret;
}
int s[MaxN][3],x[MaxN];
bool fl[MaxN];
int main()
{
scanf("%d",&n);
for (int j=0;j<3;j++)
for (int i=1;i<=n;i++)
scanf("%d",&s[i][j]);
for (int i=1;i<=n;i++){
if (s[i][1]%3!=2){puts("No");return 0;}
if (s[i][1]-s[i][0]==1){
if (s[i][2]-s[i][1]!=1){puts("No");return 0;}
fl[i]=0;
}else if (s[i][1]-s[i][2]==1){
if (s[i][0]-s[i][1]!=1){puts("No");return 0;}
fl[i]=1;
}else {puts("No");return 0;}
x[i]=(s[i][1]+1)/3;
if ((x[i]&1)^(i&1)){puts("No");return 0;}
}
int cnt0=0,cnt1=0;
for (int i=1;i<=n;i++)
if (i&1)cnt1+=fl[i];
else cnt0+=fl[i];
add(x[2]);
for (int i=4;i<=n;i+=2){
cnt1+=i/2-1-qry(x[i]);
add(x[i]);
}
for (int i=1;i<=n;i++)t[i]=0;
add(x[1]);
for (int i=3;i<=n;i+=2){
cnt0+=i/2-qry(x[i]);
add(x[i]);
}puts((cnt0&1)||(cnt1&1) ? "No" : "Yes");
return 0;
}
```