前几天给小朋友讲课的时候带他们打比赛做了这题。
好久没写题了居然也做对了，值得纪念。
题目链接：https://www.luogu.com.cn/problem/P6687
首先旋转$180^{\degree}$这种说法是比较毒瘤的。
选择$180^{\degree}$等同于将$2\times 2$的矩阵上下翻转后再左右翻转：
$$ \begin{bmatrix} A & B\\ C & D \end{bmatrix} \rightarrow \begin{bmatrix} C & D\\ A & B \end{bmatrix} \rightarrow \begin{bmatrix} D & C\\ B & A \end{bmatrix} $$
因此做一次操作相当于将相邻两列交换位置，列内元素再交换位置。
由于表格只有两行，所以无论怎么操作，同一列的两个元素永远是上下相邻的。
两个元素的上下关系也很好判断：
- 如果被操作了奇数次，则上下关系颠倒
- 如果被操作了偶数次，则上下关系不变
然后被操作次数的奇偶性等于初末位置差的奇偶性。
那么就很好判断是否有解了：
- 如果某两个本来上下相邻的元素后来不相邻了，那必然无解
- 如果初末位置差的奇偶性与最终状态的上下关系不符，则无解
- 否则必然有解
为什么有解？
冒泡排序的正确性告诉我们，如果能交换任意相邻两个元素，则一定可以由原数列重新排列成一个新的排列。
最少交换次数？
冒泡排序的交换次数等于数列中逆序对的个数。
那么问题迎刃而解。
由于数据大小$10^6$毒瘤卡常，因此用树状数组求逆序对，比归并排序常数小。
另外还需要快读，不然会超时。
代码：
#include <bits/stdc++.h>
#define NS (1000005)
#define ABS(x) ((x) > 0 ? (x) : (-(x)))
#define lowbit(x) ((x) & (-(x)))
using namespace std;
template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}
int n, D[NS], M[NS << 1], Q[NS], t[NS];
inline void add(int x)
{
while (x <= n)
{
t[x] += 1;
x += lowbit(x);
}
}
inline int query(int x)
{
int res = 0;
while (x)
{
res += t[x];
x -= lowbit(x);
}
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i += 1) IN(D[i]), M[D[i]] = i;
for (int i = 1, j; i <= n; i += 1) IN(j), M[j] = i;
for (int i = 1, j; i <= n; i += 1)
{
scanf("%d", &j);
Q[i] = M[j];
if (!((D[M[j]] == j) ^ (ABS(M[j] - i) & 1))) { puts("dldsgay!!1"); return 0; }
}
for (int i = 1, j; i <= n; i += 1)
{
scanf("%d", &j);
if (Q[i] != M[j]) { puts("dldsgay!!1"); return 0; }
}
long long ans = 0;
for (int i = n; i >= 1; i -= 1) ans += query(Q[i]), add(Q[i]);
printf("%lld\n", ans);
return 0;
}另外听某位不愿透露姓名的 boshi 说，这题是 atcoder 某题的弱化版，原题是$3\times n$的表格。
三行问题不大，中间一行可以直接删了不会有影响。
但是现在有个问题：交换的不是相邻两列，而是间隔了一列的两列。
那么就对列进行奇偶划分，分别求逆序对。
因为奇数列永远不可能成为偶数列，偶数列也不可能成为奇数列。
最重要的问题是两个奇数列交换时会对中间偶数列产生影响（中间偶数列会发生上下翻转）。
解决方法是首先判断奇数列是否合法。
然后再在归并排序求逆序对的时候求出每个偶数列被奇数列的逆序对覆盖了多少次，在判断奇偶性的时候把这个次数考虑进去就行了。
代码没写，口头 AC (光速逃