逆序,奇偶性分析
Simultaneous Swap
题目链接:https://atcoder.jp/contests/abc296/tasks/abc296_f
题意:给定两个长度都为n的序列$A,B$.你可以进行以下操作任意次,选取一组$i,j,k$,满足$i,j,k\in(1,n),i\neq j,k$,并交换$A_i,A_j$与$B_i,B_k$.请问是否可以最后将$A,B$序列变为相等.序列长度$n\in(1,2e5)$
分析:常规的构造想不出来,太菜了.但是这并不是一道构造题.
首先分析两个序列中的元素个数是否相同,如果不同那肯定不行.
如果$A,B$两个序列最后可以转化为相等,那么一定可以将他们同时转化为升序序列.反之也是同样,如果两个序列能被同时转化为升序,那么他们一定满足要求.
从升序的角度来观察一次交换的结果,如果交换的两个数相等,那么和不操作也没有什么区别.如果两数不同,一定会改变当前序列逆序对数,本质上是改变了序列逆序的奇偶性.
如果两个序列的逆序奇偶性相同,那么一定可以将他们的逆序数变得相等,再将逆序数一起归0,最后就得到了相等的上升序列.如果两个序列的逆序奇偶性不同,那么可以感性理解一下,两个序列一定无法全等.
还有一个额外的情况,如果任一序列中存在相等的元素,那么就可以在这个序列奇偶性不变的情况下改变另一个的奇偶性,保证能得到逆序数奇偶相同的序列,一定有解.