Triple Shift
来源：Atcoder ARC 136
B - Triple Shift (atcoder.jp)
题解：这道题我们不可能去硬模拟（大多数这种题都不能这样去模拟的），然后我们就要去发现特性，
发现把 ai ai+1 ai+2 变成 ai+2 ai+1 ai 的过程，并不改变这个数组中逆序对的奇偶性。 考虑把 a1...an-2 换到指定位置，那么 an-1 与 an 的相对位置将由逆序对的奇偶性直接决定。因此我们只需要判断a数组与b数组的逆序对奇偶性是否相同。 （我们可以发现，很多这种位置需要改变的题目，我们通常是去观察其奇偶性） code：#include
using namespace std;
typedef long long ll;
int i,j,k,n,m,t,a[5050],b[5050],c[5050];
int main() {
ios::sync_with_stdio(0);
cin>>n;
for(i=1;i<=n;i++){cin>>a[i];c[a[i]]++;}
for(i=1;i<=n;i++){cin>>b[i];c[b[i]]--;}
for(i=1;i<=n;i++){
if(c[i]){cout<<"No";return 0;}
}
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++){
if(a[i]>a[j])k++;
if(b[i]>b[j])k--;
if(a[i]==a[j]){
cout<<"Yes";return 0;
}
}
}
cout<<(!(k&1)?"Yes":"No");return 0; //这里是在看两者的逆序对的差是否为偶数，如果是则两者的逆序对奇偶性相同
}