ARC043 C問題 転倒距離

今までで一番WAを出したかもしれない…つらい…

ある数列A,Bが与えられて、それらから転倒距離が同じになる数列Cを出力する問題。

今回はバブルソートと関連づけられるが、あまりバブルソートのイメージで数字の大小を考えるとすごいわかりづらくなる気がする…。
A,Bでそれぞれある数字xをある数字yと入れ替えても、A,B間の転倒距離は変わらない。(だって何個入れ替わってるかだもん…)
そこでAを1,2,3…になるようにA,Bの数字をそれぞれ入れ替えていく。
そうすると、Bをバブルソートしたときの入れ替え回数と同じようにA,B間の転倒距離がわかる。(求め方は蟻本でもslideでも見て)
そうしたら元のAから元のBになるようにバブルソートしていって、転倒距離/2だけ施行したら止めてあげればそれが答え。
ここでめっちゃハマりにハマった…。
ここで言いたいのは元のAから転倒させていって元のBに近づけていくのである。
まず新しいBをバブルソートしていく。まぁBITとか使えばそこそこ綺麗にまとめられる。
そして最初、Aを1,2,3…となるように変形したが、そのオフセット分が存在するので、転倒距離/2だけバブルソートした新しいBを1,2,3…がAになるように変形してあげれば良い。

この最後のとろこで頭がぐちゃぐちゃになってすごい時間を要した…反省…

struct BinaryIndexedTree{
    int N;
    std::vector<int> bit; //1-indexed つまり1~Nを使う
    BinaryIndexedTree(int n): N(n), bit(n+1, 0){}
    void add(int a, int w){
        for(int x = a; x <=N; x+=x&(-x)) bit[x] += w;
    }
    int sum(int a){ //1~aまでsum
        int ret = 0;
        for(int x = a; x>0; x-=x&(-x)) ret += bit[x];
        return ret;
    }
};
constexpr int N_MAX = 100100;

int A[N_MAX], B[N_MAX], rA[N_MAX], nB[N_MAX], rB[N_MAX];
int memo[N_MAX], res[N_MAX];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N; cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) cin >> B[i];
    for(int i=1; i<=N; i++) rA[A[i]] = i;
    for(int i=1; i<=N; i++) nB[i] = rA[B[i]];
    for(int i=1; i<=N; i++) rB[nB[i]] = i;

    BinaryIndexedTree BitB(N);
    ll changeB = 0;
    {
        for(int i=1; i<=N; i++){
            changeB += i-1-BitB.sum(rB[i]);
            BitB.add(rB[i], 1);
        }
    }
    if(changeB%2 != 0){
        cout << -1 << endl;
        return 0;
    }

    ll change = changeB/2;
    BinaryIndexedTree Bit2(N);
    for(int i=N; i>=1; i--){
        memo[i] = Bit2.sum(rB[i]);
        Bit2.add(rB[i], 1);
    }

    //実際にバブルソート
    int cur = 1;
    while(true){
        if(memo[cur] < change){
            change -= memo[cur];
            res[cur] = cur;
        }else{
            int j = cur;
            for (int i = 1; i <= N; i++) {
                if (nB[i] >= cur) res[j++] = nB[i];
            }
            int index = 0;
            for (; res[index] != cur; index++);
            while (change) {
                if (res[index] < res[index-1]) change--;
                swap(res[index], res[index-1]);
                index--;
            }
            break;
        }
        cur++;
    }

    for(int i=1; i<=N; i++){
        cout << A[res[i]] << (i == N ? "\n" : " ");
    }
    return 0;
}