题解：CF2101B Quartet Swapping

· · 题解

看题！

对一个排列 a 可以交换 a_i 和 a_{i+2}，以及 a_{i+1} 和 a_{i+3}。不限交换次数，求字典序最小的排列。

怎么做？

对于 [1, 2, 3, 4, 5] 这个序列，我们对第 1 个位置进行操作，会得到 [3, 4, 1, 2, 5]，而此时我们再对第 2 个位置进行操作，会得到 [3, 2, 5, 4, 1]。发现了吗？2 和 4 的位置没有变，而“1 3 5”变成了“3 5 1”，相当于这三个数循环向后移了一位。
由此我们可以发现，在所有的奇数位或偶数位上的数字，我们可以任意交换数字，把小数往前移，而只剩下最后有两个数不能一定做到升序排列，即大数在前，小数在后（这就是逆序对）。
我们可以分别对奇数位和偶数位上的数进行排序，再考虑最后的数能不能按照题目的要求构造出。
如果原排列中奇数位上的逆序对个数和偶数位上的逆序对个数奇偶性相同时，要么都有奇数个逆序对，或都有偶数个逆序对。
如果都有偶数个逆序对，那我们可以直接通过“循环移位”的方式做到奇数位上的数和偶数位上的数升序。如果都有奇数个逆序对，那么最后四个数肯定是 [大数_奇,大数_偶,小数_奇,小数_偶] 或者奇偶相反一下。我们对倒数第四个数（即 a_{n-3} ）进行操作，就能得到 [小数_奇,小数_偶,大数_奇,大数_偶] 了。这两种情况都能按照题目的要求构造出。
那奇偶性不同时，就会有其中一个数位上的逆序对数比另一个数位上的多一个，这种情况下分别对两个数位上的数进行排序，就不符合题目的要求了（排序后就没有逆序对了）。这时我们只需交换一下 a_n 和 a_{n-2}，“还给他”一个逆序对就可以了。

我们使用归并排序，就可以在排序的同时求出逆序对的个数了。

上代码！

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define foru(a,b,c) for(ll a=b;a<=c;a++)

ll a[1000005],b[500005],c[500005],t[500005],ans;

void binarysortb(ll l,ll r){
    if(l>=r)return;
    ll mid=(l+r)>>1;
    binarysortb(l,mid);
    binarysortb(mid+1,r);
    ll i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
        if(b[i]<=b[j])t[k++]=b[i++];
        else t[k++]=b[j++],ans+=mid-i+1;
    while(i<=mid)t[k++]=b[i++];
    while(j<=r)t[k++]=b[j++];
    for(ll i=l;i<=r;i++)b[i]=t[i];
}

void binarysortc(ll l,ll r){
    if(l>=r)return;
    ll mid=(l+r)>>1;
    binarysortc(l,mid);
    binarysortc(mid+1,r);
    ll i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
        if(c[i]<=c[j])t[k++]=c[i++];
        else t[k++]=c[j++],ans+=mid-i+1;
    while(i<=mid)t[k++]=c[i++];
    while(j<=r)t[k++]=c[j++];
    for(ll i=l;i<=r;i++)c[i]=t[i];
}

int main(){
    ll n,bcnt=0,ccnt=0,ans2;
    cin>>n;
    foru(i,1,n)cin>>a[i];
    for(ll i=1;i<=n;i++)//分离奇偶数位上的数
        if(i%2==1)b[++bcnt]=a[i];
        else c[++ccnt]=a[i];
    binarysortb(1,bcnt);//奇数位上的数的归并排序
    ans2=ans;
    ans=0;
    binarysortc(1,ccnt);//偶数位上的数的归并排序
    if(abs(ans-ans2)&1)//逆序对数量的奇偶性不同
        if(n%2)swap(b[bcnt-1],b[bcnt]);
        else swap(c[ccnt-1],c[ccnt]);
    foru(i,1,n)//合并输出
        if(i%2==1)cout<<b[(i+1)/2]<<" ";
        else cout<<c[i/2]<<" ";
    return 0;
}