题意简述
给定两个长度为 $n$ 的不同正整数数组 $a$ 和 $b$，我们希望将两个数组变得相同。当两个长度为 $k$ 的数组 $x$ 和 $y$ 满足对于所有的 $1 \le i \le k$，都有 $x_i = y_i$ 时，称这两个数组相同。
现在，在一步操作中，你可以选择数组 $a$ 中的某个索引 $l$ 和 $r$（$l \le r$）并交换 $a_l$ 和 $a_r$，然后选择数组 $b$ 中的某个索引 $p$ 和 $q$（$p \le q$），使得 $r-l = q-p$ 并交换 $b_p$ 和 $b_q$。
是否有可能通过这些操作使两个数组变得相同？
思路分析
与 CF1983B 的解决思路有一些类似。（是因为是同一场比赛吗👉👈）
首先我们可以排除两个序列的组成元素也不相同的情况。将两个数组排序后依次比对即可。
考虑每次的交换操作是否具有可累加性，即对某对索引进行一次交换操作是否可以通过若干次对其子区间内的索引的交换操作得到。
这点是显然的。因为可以将 $ai$ 与 $a{i+1}$ 交换，递推若干次得到目标操作。
又由于这个操作可逆，所以与其看作将 $a$ 通过变换得到 $b$，不如看作 $a$ 与 $b$ 都各自进行一些操作达到某个固定的结果。这里我们令这个结果为整个序列升序排列。
那么原题就可以转化为，对于一个序列 $a$，最少通过多少次交换相邻元素使其变得有序？
聪明的读者肯定发现了，这是一个冒泡排序。
更聪明的读者肯定发现了，这实际上是在求一个序列的逆序对对数。
冒泡排序对该问题的求解复杂度是 $O(N^2)$ 的，对于这个问题的 $N \le 10^5$ 显然会超时。
那么我们可以掏出来树状数组以 $O(N\log N)$ 的复杂度求逆序对。这里不做更多说明。
我们现在知道了 $a$ 和 $b$ 分别需要多少次操作来达到有序状态。
但又由题面知，$a$ 与 $b$ 每次交换元素的间距是相同的，即它们所需的操作总数是相同的。
那么二者的总操作数必定为偶数。
检查二者的逆序对数和是否为偶数即可。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include<bits/stdc++.h>
using namespace std;
const int maxN = 2e5 + 10;
int A[maxN];
int B[maxN];
#define lowbit(x) ((x) & (-x))
struct BIT{
long long data[maxN << 2];
int N;
BIT(){};
inline void add(int x, int value){
while (x <= maxN)
{
data[x] += value;
x += lowbit(x);
}
}
inline long long query(int x){
long long result = 0;
while (x)
{
result += data[x];
x -= lowbit(x);
}
return result;
}
}bit;
inline void solve(){
int N;
scanf("%d",&N);
bit.N = N;
long long num1 = 0;
long long num2 = 0;
for(int i = 1;i<=N;i++){
int t;
scanf("%d",&t);
A[i] = t;
num1 += i-bit.query(t);
bit.add(t,1);
}
for(int i = 1;i<=N;i++) bit.add(A[i],-1);
for(int i = 1;i<=N;i++){
int t;
scanf("%d",&t);
B[i] = t;
num2 += i-bit.query(t);
bit.add(t,1);
}
for(int i = 1;i<=N;i++) bit.add(B[i],-1);
sort(A+1,A+1+N);
sort(B+1,B+1+N);
for(int i = 1;i<=N;i++){
if(A[i] != B[i]){
printf("NO\n");
return;
}
}
long long ans = abs(num1-num2);
if(ans % 2 == 1) printf("NO\n");
else printf("YES\n");
}
int main(){
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
|