ARC080 E Young Maids

問題

https://beta.atcoder.jp/contests/arc080/tasks/arc080_c

 

辞書順最小を作りたかったら出来るだけ小さいものを置いていく貪欲で上手くいくので,その方針でかんがえる.

あるペアを先頭に置ける条件をかんがえると,(偶数長の列)A(偶数長の列)B(偶数長の列)となっていればABを先頭に置けることがわかる.よってAは奇数番目の要素,BはAよりうしろにある偶数番目の要素でなければならない.

そこで奇数番目の要素の中の最小値をさがし,そのうしろにある偶数番目の要素の中の最小値をさがすことで先頭に来るペアを決定することが出来る(与えられる数列は1~Nの順列であるから同じ要素が2つ以上含まれることがないのが嬉しい).

この2つの要素を消すと,数列は高々3つの区間に分割され,区間内でペアを作るのは自由だが,区間をまたいでペアを作ることは出来ないという状況になる.

あとは各区間について同じことをやって次に置ける最小ペアを見つけては置くということを繰り返すだけなのだが,ここを高速化したい.

たくさん区間があるとき,次に置ける最小ペアを含んでいる区間をどう見つければよいのだろうか.それは簡単で,各区間内の奇数番目の要素の最小値をあらかじめ計算してタグをつけておき,そのタグが最小である区間を選んでくれば良い.これはプライオリティーキューで高速に実現できる.

あとはその区間内ではじめに説明したようにペアを作って区間を分割し,分割された各区間について新たにタグをつけてやればいい.奇数番目,偶数番目の要素の最小値を計算するパートは,RMQのセグメント木で出来る.結局,区間を選んでくる操作はN/2回行い,各区間についてO(logN)の操作を行うので全体の計算量はO(Nlog^2N)になって間に合う.

割とすんなり難しい問題が通せるようになってきていて嬉しい.

 ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
typedef pair<int, int> P;
typedef pair<int, int> R1;
typedef pair<P, R1> R2;
struct RMQ {
    P *data;
    int size;
    RMQ(int n) {
        size = 1;
        while (size < n) size *= 2;
        data = new P[size * 2 - 1];
        for (int i = 0; i < size * 2 - 1; i++) data[i] = P(1 << 30, -1);
    }
    void update(int k, P p) {
        k += size - 1;
        data[k] = p;
        while (k > 0) {
            k = (k - 1) / 2;
            data[k] = min(data[k * 2 + 1], data[k * 2 + 2]);
        }
    }
    P query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return P(1 << 30, -1);
        if (a <= l && r <= b) return data[k];
        P vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        P vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
};
int p[200000];
int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> p[i];
    RMQ odd(N), even(N);
    for (int i = 0; i < N; i++) {
        if (i & 1) odd.update(i, P(p[i], i));
        else even.update(i, P(p[i], i));
    }
    P mv = even.query(0, N, 0, 0, odd.size);
    priority_queue<R2, vector<R2>, greater<R2>> Q;
    Q.emplace(mv, R1(0, N));
    vector<int> ans;
    while (!Q.empty()) {
        R2 r = Q.top(); Q.pop();
        ans.push_back(r.first.first);
        P t1, t2;
        if (r.second.first & 1) {
            t1 = even.query(r.first.second, r.second.second, 0, 0, even.size);
        }
        else {
            t1 = odd.query(r.first.second, r.second.second, 0, 0, odd.size);
        }
        ans.push_back(t1.first);
        if (r.second.first < r.first.second) {
            if (r.second.first & 1)  t2 = odd.query(r.second.first, r.first.second, 0, 0, even.size);
            else t2 = even.query(r.second.first, r.first.second, 0, 0, odd.size);
            Q.emplace(t2, R1(r.second.first, r.first.second));
        }
        if (t1.second + 1 < r.second.second) {
            if (t1.second & 1)  t2 = even.query(t1.second + 1, r.second.second, 0, 0, even.size);
            else t2 = odd.query(t1.second + 1, r.second.second, 0, 0, odd.size);
            Q.emplace(t2, R1(t1.second + 1, r.second.second));
        }
        if (r.first.second + 1 < t1.second) {
            if (r.first.second & 1) t2 = even.query(r.first.second + 1, t1.second, 0, 0, even.size);
            else t2 = odd.query(r.first.second + 1, t1.second, 0, 0, odd.size);
            Q.emplace(t2, R1(r.first.second + 1, t1.second));
        }
    }
    cout << ans[0];
    for (int i = 1; i < ans.size(); i++) cout << " " << ans[i];
    cout << endl;
}