题解 AT4363 【[ARC102D] Revenge of BBuBBBlesort!】

· · 题解

题意：给出一个长度为 n 的排列 p，每次操作你可以选择三个连续的数 p_{i-1},p_i,p_{i+1}，并交换 p_{i-1} 与 p_{i+1}，问是否能够通过若干次操作使得 p_i=i。

数据范围 1 \leq n \leq 3 \times 10^5。

这应该是昨晚华二讲的几道题里面实现起来最简单的一道题了。我的题解相当于在翻译zjc巨佬的题解

首先我们需要寻找不变量，不难发现每一次交换以后，会有三对逆序对消失：

而最后得到的 p_i=i 的排列恰满足逆序对数量为 0，也就是说我们需要判断逆序对数量是否为 3 的倍数。

但是这样还是远远不够的。

\texttt{Hack:} 
4 3 2 1

这个排列的逆序对数量为 \frac{4 \times (4-1)}{2}=6 为 3 的倍数不过我们还是不可以把它变为 p_i=i。

还可以发现，不管怎么换奇数位上的数到不了偶数位，偶数位上的数到不了奇数位，所以我们还需检查奇数位上的数是否都是奇数，偶数位上的数是否都是偶数。

不过还是可以 \texttt{Hack:}

7 6 5 4 3 2 1

怎么办呢？它又假了

如果我们把奇数位想象成一个序列，偶数位想象成一个序列。那么一次交换要么奇数位上逆序对个数减 1，要么偶数位上逆序对个数减 1，又根据每次任意操作一个位置整个序列的逆序对个数最多减少 3，所以我们还需判断奇数位逆序对个数加偶数位逆序对个数是否等于整个序列逆序对个数的 \frac{1}{3}，就可以过了。

//Coded by tzc_wk
/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include <bits/stdc++.h>
using namespace std;
#define fi          first
#define se          second
#define fz(i,a,b)   for(int i=a;i<=b;i++)
#define fd(i,a,b)   for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a)      a.begin(),a.end()
#define giveup(...) return printf(__VA_ARGS__),0;
#define fill0(a)    memset(a,0,sizeof(a))
#define fill1(a)    memset(a,-1,sizeof(a))
#define fillbig(a)  memset(a,0x3f,sizeof(a))
#define fillsmall(a) memset(a,0xcf,sizeof(a))
#define mask(a)     (1ll<<(a))
#define maskx(a,x)  ((a)<<(x))
#define _bit(a,x)   (((a)>>(x))&1)
#define _sz(a)      ((int)(a).size())
#define filei(a)    freopen(a,"r",stdin);
#define fileo(a)    freopen(a,"w",stdout);
#define fileio(a)   freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define put(x)      putchar(x)
#define eoln        put('\n')
#define space       put(' ')
#define y1          y_chenxiaoyan_1
#define y0          y_chenxiaoyan_0
typedef pair<int,int> pii;
inline int read(){
    int x=0,neg=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  neg=-1;
        c=getchar();
    }
    while(isdigit(c))   x=x*10+c-'0',c=getchar();
    return x*neg;
}
inline void print(int x){
    if(x<0){
        putchar('-');
        print(abs(x));
        return;
    }
    if(x<=9)    putchar(x+'0');
    else{
        print(x/10);
        putchar(x%10+'0');
    }
}
inline int qpow(int x,int e,int _MOD){
    int ans=1;
    while(e){
        if(e&1) ans=ans*x%_MOD;
        x=x*x%_MOD;
        e>>=1;
    }
    return ans;
}
int n=read(),a[300005];
struct Fenwick_Tree{
    int bit[300005];
    Fenwick_Tree(){fill0(bit);}
    inline void add(int x){
        for(int i=x;i<=n;i+=(i&(-i)))   bit[i]++;
    }
    inline int sum(int x){
        int ans=0;
        for(int i=x;i;i-=(i&(-i)))  ans+=bit[i];
        return ans;
    }
};
inline vector<int> calc(vector<int> t){
    vector<int> v;Fenwick_Tree Bit;
    foreach(it,t){
        v.push_back(Bit.sum(n)-Bit.sum(*it));
        Bit.add(*it);
    }
    return v;
}
signed main(){
    fz(i,1,n)   a[i]=read();
    for(int i=1;i<=n;i+=2)  if(a[i]&1^1)    return puts("No"),0;
    for(int i=2;i<=n;i+=2)  if(a[i]&1)      return puts("No"),0;
    vector<int> b,b1,b2;
    for(int i=1;i<=n;i+=2)  b1.push_back(a[i]); 
    for(int i=2;i<=n;i+=2)  b2.push_back(a[i]); 
    for(int i=1;i<=n;i++)   b.push_back(a[i]);  
    vector<int> c=calc(b),c1=calc(b1),c2=calc(b2);
    int sum1=0,sum2=0,sum3=0;
    foreach(it,c)   sum1+=*it;
    foreach(it,c1)  sum2+=*it;
    foreach(it,c2)  sum3+=*it;
    if(sum1==(sum2+sum3)*3) puts("Yes");
    else                    puts("No");
    return 0;
}