ARC102D

考虑一次交换操作从 \(c,b,a\) 变成 \(a,b,c\)，减少了 \(3\) 对逆序对 \((c,b),c(c,a),(b,a)\)，然后一次操作也不会改变一个点的位置的奇偶性。

这指明了两条信息：

• 点权与位置的奇偶性应当相同。
• 逆序对的对数应当是 \(3\) 的倍数。

当然，只有这两个条件是远远不够的，然后还可以发现每一次操作，会减少一对奇偶性相同的逆序对。

所以奇数与偶数的逆序对数之和应当是逆序对的三分之一。

Code

Code

#include <bits/stdc++.h>

const int maxn = 3e5 + 10;

int n, tmp;
struct Tree
{
	int t[maxn], ans;
	
    Tree () {
        memset (t, 0, sizeof t);
        ans = 0;
    }
	inline int lowbit(int x)
	{
		return x & -x;
	}

	inline void update(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;
	}
} T[3];

inline int read()
{
	int x(0);
	char o(getchar());
	while (o < '0' || o > '9') o = getchar();
	for (; o >= '0' && o <= '9'; o = getchar())
	   x = (x << 1) + (x << 3) + (o ^ 48);
	return x;	
}

int main()
{
    n = read();

	for (int i = 1; i <= n; ++i) {
		tmp = read();

		T[i & 1].ans += T[i & 1].query(n - tmp + 1);
		T[2].ans += T[2].query(n - tmp + 1);
		
		T[i & 1].update(n - tmp + 1);
		T[2].update(n - tmp + 1);

		if ((tmp & 1) ^ (i & 1)) {
			puts("No");
			return 0;
		}
	}

	if (T[2].ans == (T[0].ans + T[1].ans) * 3) {
		puts("Yes");
	} else puts("No");
}