题解：CF2060G Bugged Sort

· · 题解

有意思的简单题。

判定能否通过某种操作达到确定状态的题目，我们可以尝试进一步简化操作。显然每一列是 a_i,b_i 或 b_i,a_i，不妨将列内序与列间序分开考虑。

由于我们可以同时改变列内序和列间序，所以我们考虑如何只改变列间序（列内序）。事实上，对于两列 i,j，只需要引入第三列 k，依次交换 (i,k),(k,j),(i,k) 即可只改变列间序。

但是由于每次改变两列的列间序，所以一定只能列间序改变偶数列。

于是问题变成了若干对 (a_i,b_i)，任意排序，可以进行偶数次内部交换，要求分别 a,b 递增。考虑贪心，先不考虑内部交换偶数次的限制，对于每一对都使 a_i<b_i，直接看成线段排序，依次枚举即可。如对于线段 (1,b_1)，若 b_1>2，则第二条线段一定是 (2,b_2)，其中 b_2>b_1，否则无解，以此类推。

考虑内部序，注意到对于线段有交的连通块，第一条线段的内部序定后，后面的实际上都已经确定，所以每次只能同时翻转一个连通块。假设我们已经排序，对于总次数的奇偶性，偶长块不改变，奇长块一定改变，所以要么初始为偶数，要么存在奇长块。

代码比 dp 好写一些。

#include<bits/stdc++.h>
#define maxn 210005
#define fi first
#define se second
using namespace std;
const int inf=1e9;

int n,id[maxn];
pair<int,int>p[maxn];
inline void solve(){
    int sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&p[i].fi);
    for(int i=1;i<=n;i++) scanf("%d",&p[i].se),id[i]=i;
    for(int i=1;i<=n;i++) if(p[i].fi>p[i].se) swap(p[i].fi,p[i].se),sum^=1;
    sort(id+1,id+n+1,[](int x,int y){return p[x]<p[y];});
    int r=0,cnt=0,fl=0;
    p[id[n+1]=n+1].fi=inf;
    for(int it=1,i=id[it];it<=n+1;it++,i=id[it]){
        if(p[i].fi<=r){
            if(p[i].se<r) return puts("NO"),void();
            r=p[i].se;
            cnt^=1;
            continue;
        }
        if(it!=1) fl|=cnt;
        cnt=1,r=p[i].se;
    }
    puts(sum&&!fl?"NO":"YES");
}
signed main(){
    signed T=1;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}