传送门

全程智障。。。明明已经推出来正解的结论了,然而却一直在想怎么算每一位取反了多少次,没发现直接算异或和就行了。。。就这么完美避开了正解,中间其实想了一个$O(n\log n)$的做法,是强行算出冒泡排序时每一个位置交换多少次,要用平衡树+线段树维护。因为自己知道肯定不是正解,所以就没写了。。。

这题的结论比较隐蔽,但还是能看得出来的(然而看出来了还是傻逼地不会做)。考虑进行一次操作,其实就是把隔着一列的两列交换,并把这三列都进行上下翻转。记某一列$a$上下翻转后为$\bar a$,我们可以通过构造一系列操作,把$abcde$变成$a\bar bc\bar de$,也可以变成$\bar ab\bar cde$和$ab\bar cd\bar e$(这个构造我是碰运气瞎转转出来的233)。这样的话,只要两个位置的奇偶性相同(不相邻的话可以一个个翻转过去),我们就可以同时对他们进行翻转。根据这个结论,只要我们知道奇数位上(并且偶数位上也成立)需要翻转的总次数是偶数,就一定不会出现最后剩下某些位置翻不过来的情况。

进行一次操作的时候,我们会把两个距离为2的列交换,同时把中间夹着的那一列翻转。这意味着我们在对奇数位上的数顺序进行排序时,在偶数位上进行翻转的次数的奇偶性一定跟奇数位上的逆序对数的奇偶性相同(把偶数位和奇数位反过来也成立)。而逆序对数是确定的,所以对奇数位(或偶数位)上进行翻转的次数的奇偶性也是确定的。这样的话,前面的那个条件就变成充分必要条件了。所以我们只需要分别求出奇数位上和偶数位上的逆序对数的奇偶性,就可以判断出结果了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100010
using namespace std;

int n;
int d[MAXN];
int a[MAXN];
int a0[4][MAXN];

namespace Fenwick{
    int c[MAXN];

    void clear(){ memset(c,0,sizeof c); }

    void add(int x,int v){
        while(x<=n){
            c[x]+=v;
            x+=x&(-x);
        }
    }

    int sum(int x){
        int res=0;
        while(x){
            res+=c[x];
            x-=x&(-x);
        }
        return res;
    }
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a0[1][i]);
    for(int i=1;i<=n;i++) scanf("%d",&a0[2][i]);
    for(int i=1;i<=n;i++) scanf("%d",&a0[3][i]);
    int t0=0,t1=0;
    for(int i=1;i<=n;i++){
        int v1=min(a0[1][i],a0[3][i]),v3=max(a0[1][i],a0[3][i]);
        a[i]=v1/3+1;
        if(v3!=v1+2 || v1%3!=1 || a0[2][i]!=v1+1 || (a[i]-i)%2!=0){
            puts("No");
            return 0;
        }
        if(v1==a0[3][i]){
            if(i&1) t1^=1;
            else t0^=1;
        }
    }
    for(int i=n-((n&1)^1);i>=1;i-=2){
        int temp=Fenwick::sum(a[i]);
        Fenwick::add(a[i],1);
        if(temp&1) t0^=1;
    }
    Fenwick::clear();
    for(int i=n-(n&1);i>=2;i-=2){
        int temp=Fenwick::sum(a[i]);
        Fenwick::add(a[i],1);
        if(temp&1) t1^=1;
    }
    if(t0 || t1) puts("No");
    else puts("Yes");
    return 0;
}