問題

C: 転倒距離 - AtCoder Regular Contest 043 | AtCoder

問題概要

$1$ から $N$ までの整数を並び替えたものをサイズ $N$ の順列として，サイズ $N$ の順列 $X$ と $Y$ に対して，その2つで順序が入れ替わっている数字の組の個数を $X$ と $Y$ の転倒距離とするときに， $X$ とも $Y$ とも転倒距離の等しいサイズ $N$ が存在するかを判定し，存在するならそのうちの1つを答えよ．

$1 \le N \le 10^5$

アイデア

まず， $X$ と $Y$ の転倒距離を $T(X,Y)$ と表すことにしよう．すると， $T(X,Z) = T(Y,Z)$ なる $Z$ が存在するなら $Z$ が答えになる．またこのような $Z$ が存在する時， $T(X,Y)$ は偶数になる．まずこれを示す．

サイズ $N$ の順列について，数字の組は $\frac{n(n-1)}{2}$ 個あるが，その各組について，次の4通りに分かれる：

$X$ と $Z$ では違う並び， $Y$ と $Z$ でも違う並び
$X$ と $Z$ では違う並び， $Y$ と $Z$ では同じ並び
$X$ と $Z$ では同じ並び， $Y$ と $Z$ では違う並び
$X$ と $Z$ では同じ並び， $Y$ と $Z$ でも同じ並び

この4通りについて，各組の個数をそれぞれ $x_1 , x_2 , x_3 , x_4$ とすると， $T(X,Z) = x_1 + x_2 , T(Y,Z) = x_1 + x_3$ となる．そして， $T(X,Y) = x_2 + x_3$ であるから， $T(X,Z)$ と $T(T,Z)$ を使って表すと， $T(X,Y) = T(X,Z) + T(Y,Z) - 2*x_1$ となる．更にいま $T(X,Z) = T(Y,Z)$ であるから， $T(X,Y)$ は偶数になる．

対偶を取れば $T(X,Y)$ が奇数ならば $T(X,Z) = T(Y,Z)$ なる $Z$ が存在しないとなる．以下，解が存在する場合について考えていくことにする．

まず，数字の大小は影響しないので， $X$ の方を昇順になるように数字を変換する．すると， $X$ はソートされた形になり， $Y$ との転倒距離の見通しが立てやすい．具体的には， $Y$ の各要素について，それよりも左側にあるその要素より大きい物を数え上げれば転倒距離を計算できる．そして，これは転倒数として知られており，バブルソートにおける交換回数と一致することが知られている．

すると，予め転倒数を計算してその転倒数を $a$ とすると $\frac{a}{2}$ 回交換されるまでバブルソートをすることで $O(N^2)$ の解答が得られるが，これでは速度が足りない．

バブルソートを逐一やっているのでは間に合わないので，ある程度まとめることを考える．バブルソートの過程を見ると，各過程において，その数字がしかるべき位置までにスワップが発生する回数は最初の数列の状態でその数よりも左にある数でその数よりも大きい数の個数に一致することに気づく．

それを逐次更新しながら，個数を高速に数え上げるためにはBITやSegtreeが有効である．よって，この部分の実装の流れとしては，まずSegtreeを使いながら転倒数を逐次更新していき，まず全体の転倒数 $a$ を求め，そこから $\frac{a}{2}$ を越えないように1つずつバブルソートを進めていって越えそうになる直前でバブルソートに切り替えて $\frac{a}{2}$ に到達させればよいということになる．

また，転倒数がint型に収まらない可能性があるので注意(そのミスでで30分くらいバグをさがしつづけた)

実装(C++)

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

struct SumSegTree{
    long n; vector<ll> dat;
    //初期化
    SumSegTree(long _n){
        n=1;
        while(n<_n) n*=2;
        dat=vector<ll>(2*n-1,0);
    }
    //k番目(0-indexed)の値をaに変更
    void update(long k, ll a){
        k+=n-1;
        dat[k]=a;
        //更新
        while(k>0){
            k=(k-1)/2;
            dat[k]=dat[2*k+1]+dat[2*k+2];
        }
    }
    //内部的に投げられるクエリ
    ll _query(long a, long b, long k, long l, long r){
        if(r<=a || b<=l) return 0;

        if(a<=l && r<=b) return dat[k];
        else{
            ll vl=_query(a,b,2*k+1,l,(l+r)/2);
            ll vr=_query(a,b,2*k+2,(l+r)/2,r);
            return vl+vr;
        }
    }
    //[a,b)の和を求める
    ll query(long a, long b){
        return _query(a,b,0,0,n);
    }
};

int main()
{
    int n;
    cin >>n;
    vector<int> x(n),y(n);
    rep(i,n) scanf(" %d", &x[i]);
    rep(i,n) scanf(" %d", &y[i]);

    //aが昇順になるように変換
    vector<int> f(n+1);
    rep(i,n) f[x[i]]=i+1;
    rep(i,n) y[i]=f[y[i]];

    SumSegTree s(n+2);
    vector<int> num(n+1);
    rep(i,n)
    {
        num[y[i]]=s.query(y[i]+1,n+1);
        s.update(y[i],1);
    }

    //転倒数
    ll a=0;
    rep(i,n) a+=num[i+1];

    //存在しない場合
    if(a%2==1)
    {
        printf("-1\n");
        return 0;
    }

    //存在する場合
    ll ct=0;
    int now=0;
    while(now<n)
    {
        if(ct+num[now+1]>=a/2) break;

        ct+=num[now+1];
        ++now;
    }

    //答えになる数列
    vector<int> z;
    rep(i,now) z.pb(i+1);
    rep(i,n) if(y[i]>now) z.pb(y[i]);

    for(int i=n-1; i>now; --i)
    {
        if(z[i]<z[i-1])
        {
            swap(z[i],z[i-1]);
            ++ct;
        }
        if(ct==a/2) break;
    }

    rep(i,n)
    {
        if(i) printf(" ");
        //元の数値に変換して表示
        printf("%d", x[z[i]-1]);
    }
    printf("\n");
    return 0;
}