Valley: matrix rotation

It can be found by observation that:

For such a two column table, a 180 ° rotation of a 2x2 square is equivalent to the exchange of upper left and lower right, lower left and upper right

And this exchange won't change anything? Two numbers in any column will not be changed!

But it will change the positional relationship between the two numbers, turning them upside down once

So we get the first condition to judge that there is no solution:

If two numbers in any column of the original state are not in the same column in the target state, there is obviously no solution

Then, after excluding the above situations without solutions, we can find that:

If the corresponding positions of two numbers in any column of the original state are different in the target state, the existence of the solution will also change!

2 / 3 2/3 2 / 3 to be converted into 3 / 2 3/2 The number of 3 / 2 Intermediate rotations is obviously odd!

Similarly, if the up-down relationship between the original state and the target state does not change, the number of rotations is even

If this parity is not satisfied, there is obviously no solution

------------------—

To sum up, we have finally discussed the judgment of whether there is a solution or not

How to find the minimum number of rotations?

It can be observed that the rotation of two numbers in the same column is bound together and will not change, so a column can be regarded as a number

This translates into:

Convert a column of numbers in the original state into a column of numbers in the target state, and ask the minimum number of steps of conversion (the conversion method is to exchange any two adjacent columns of numbers)

Through experience, we know that the number of reverse order pairs in a sequence (mapped from the master) = = the minimum number of steps of the sequence from the master

Therefore, the above code:

#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define ul (u << 1)
#define ur (u << 1 | 1)
#define fx first
#define fy second
//#pragma GCC optimize(2)
//[blog address]( https://blog.csdn.net/weixin_51797626?t=1) 
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int N = 1000010, M = 110, MM = 3000010;
int INF = 0x3f3f3f3f, mod = 100003;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S, D;
struct arr
{
	int row, col;
}ch[N << 1];//Open it up!!! It's too small to make any mistakes di re ctly
int b[3][N], z[N], tmp[N];

bool check() {
	for (int j = 1; j <= n; j++) {
		int b1 = b[1][j], b2 = b[2][j];
		if (ch[b1].col != ch[b2].col)return false;
		//First, judge whether the same column is legal
	}

	for (int j = 1; j <= n; j++) {
		int b1 = b[1][j];
		if (ch[b1].row == 1) { //Re judge parity
			if (ch[b1].col % 2 != j % 2)return false;
		}
		else {
			if (ch[b1].col % 2 == j % 2)return false;
		}
	}
	return true;
}

ll gui_sort(int l, int r) {
	if (l >= r)return 0;//Don't forget the recursive boundary, otherwise the door-to-door service will be endless

	int mid = l + r >> 1;
	ll cnt = gui_sort(l, mid) + gui_sort(mid + 1, r);

	int i = l, j = mid + 1, k = l;
	while (i <= mid && j <= r)
	{
		if (z[i] <= z[j])tmp[k++] = z[i++];
		else { 
			//Find that the first i is greater than J. obviously, all numbers after i are greater than j, and count them into the number of reverse pairs
			cnt += (ll)mid - i + 1;
			tmp[k++] = z[j++];
		}
	}
	while (i <= mid)tmp[k++] = z[i++];
	while (j <= r)tmp[k++] = z[j++];

	for (int i = l; i <= r; i++)z[i] = tmp[i];
	return cnt;
}

int main() {
	cinios;

	cin >> n;
	for (int i = 1; i <= 2; i++)
		for (int j = 1; j <= n; j++) {
			int t;
			cin >> t;
			ch[t] = { i,j };//Record the row and column information of the number of master (original state)
			//The title tells us that numbers are not heavy or missing

			//Note that there are at most 2*n numbers here The array has a small bug. Find a day
		}

	for (int i = 1; i <= 2; i++)
		for (int j = 1; j <= n; j++)
			cin >> b[i][j];//Target status

	if (!check()) {
		cout << "dldsgay!!1";
		return 0;
	}

	for (int j = 1; j <= n; j++)//The sequence mapped from the master is used to find the reverse order pair
		z[j] = ch[b[2][j]].col;

	cout << gui_sort(1, n);

	return 0;
}

------------------—

A simpler way to judge, excerpted from the solution to the question of Luogu

All numbers can be divided into two states, W and M W and M W and M

As long as the number of W runs to the position of M, or vice versa, it can be said that there is no solution

code:

#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define ul (u << 1)
#define ur (u << 1 | 1)
#define fx first
#define fy second
//#pragma GCC optimize(2)
//[blog address]( https://blog.csdn.net/weixin_51797626?t=1) 
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int N = 1000010, M = 110, MM = 3000010;
int INF = 0x3f3f3f3f, mod = 100003;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S, D;
int st[N << 1];
int a[N][2], b[N][2], z[N], tmp[N];

ll gui_sort(int l, int r) {
	if (l >= r)return 0;//Recursive boundary don't forget

	int mid = l + r >> 1;
	ll cnt = gui_sort(l, mid) + gui_sort(mid + 1, r);

	int i = l, j = mid + 1, k = l;
	while (i <= mid && j <= r)
	{
		if (z[i] <= z[j])tmp[k++] = z[i++];
		else {
			cnt += (ll)mid - i + 1;
			tmp[k++] = z[j++];
		}
	}
	while (i <= mid)tmp[k++] = z[i++];
	while (j <= r)tmp[k++] = z[j++];

	for (int i = l; i <= r; i++)z[i] = tmp[i];
	return cnt;
}

int main() {
	cinios;

	cin >> n;
	for (int i = 0; i < 2; i++)
		for (int j = 1; j <= n; j++)cin >> a[j][i];//Note that j records the up and down status before i
	for (int i = 0; i < 2; i++)
		for (int j = 1; j <= n; j++)cin >> b[j][i];

	for (int i = 1; i <= n; i++)
		st[a[i][i & 1]] = i;//Record the column in which type M is in the original status (record W can also be used)

	for (int i = 1; i <= n; ++i) {
		if (st[b[i][i & 1]])z[i] = st[b[i][i & 1]];//Handy recording sequence
		//Corresponding to the target state, see if this number is of type M
		//If not, there is no solution, because the rotation operation cannot make the number run to other states
		else {
			cout << "dldsgay!!1";
			return 0;
		}
	}

	cout << gui_sort(1, n);

	return 0;
}

Simple and beautiful