AtCoder Regular Contest 080 E - Young Maids

http://arc080.contest.atcoder.jp/tasks/arc080_c

問題概要

偶数N、1~Nの順列P、空の数列Qがある。Pが空になるまで以下の操作を行う。

操作: Pの隣り合う2要素を選び、順序を保ったままQの先頭に追加する。

これによってできるQのうち、辞書順で最小のものを求めよ。

N <= 2 * 105

解法

操作を逆順で考え、前から順に値を確定させていく。ここで逆操作は以下のように言うことができる。

  1. 「手持ちの区間」からひとつの区間[l, r]を選び、「手持ちの区間」から取り除く
  2. 選んだ区間の「先頭から数えて奇数番目の要素」をひとつ選び、そのindexをaとする
  3. 選んだ区間の「先頭から数えて偶数番目かつaより後ろにある要素」をひとつ選び、そのindexをbとする
  4. (P[a], P[b])をこの順でQの末尾に追加する
  5. 区間[l, a-1], [a+1, b-1], [b+1, r]のうち空でないものをすべて「手持ちの区間」に追加する

解を得るためには選びうる(a, b)のうちで(P[a], P[b])が辞書順最小のものを貪欲に取っていく必要がある。すなわち「手持ちの区間」のすべてについて「先頭から数えて奇数番目の要素の最小値」を調べてそれが最小となる区間を取ってくること、さらにそれに対応する偶数番目の最小値を取ってくることが必要になる。ここで「手持ちの区間」全部を毎回愚直調べているとO(N2)になって間に合わない。必要なのは以下の操作を高速に行うことである。

  1. ある区間における「先頭から奇数番目の要素の最小値」を求める
  2. ある区間における「先頭から偶数番目の要素の最小値」を求める
  3. 「手持ちの区間」の中から「先頭から数えて奇数番目の要素の最小値」が最小の区間を求める

このうち1, 2の操作はセグメント木を2本持つことで行うことができる。片方のセグメント木にはPのindexが奇数のものを詰め、もう片方には偶数のものを詰める。「先頭から奇数番目の要素の最小値」を求めたいときは区間の始まりのindexの偶奇を見、対応する方のセグ木にクエリを投げればよい。

3は「手持ちの区間」をpriority queueで管理すればよい。priority queueで見る値として、その区間の「先頭から奇数番目の要素の最小値」を入れておく。これはpriority queueに突っ込むときに一度だけ計算すればよい。

以上で区間の選択, 最小値の取得, 区間の分割の各操作がO(logN)で行え、全体としてO(NlogN)になる。

感想

やった〜〜〜〜黄色になれたよ〜〜〜〜〜〜〜〜〜〜〜〜〜〜おかあさ〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜ん

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

alias Tuple!(int, "a", int, "l", int, "r") Seg;

void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!int).array;
    auto B = new int[](N+1);
    foreach (i; 0..N) B[A[i]] = i;

    auto st1 = new SegmentTree(N + 1);
    auto st2 = new SegmentTree(N + 1);

    for (int i = 0; i < N; i += 2) st1.assign(i, A[i]);
    for (int i = 0; i < N; i += 2) st2.assign(i+1, A[i+1]);

    int query(int l, int r) {
        if (l % 2 == 0) return st1.query(l, r);
        else return st2.query(l, r);
    }

    auto ans = new int[](N);
    int p = 0;

    auto pq = new BinaryHeap!(Array!Seg, "a[0] > b[0]");
    pq.insert(Seg(query(0, N-1), 0, N-1));

    while (!pq.empty) {
        auto seg = pq.front;
        pq.popFront;
        auto l = seg.l;
        auto r = seg.r;
        int a = seg.a;
        int ai = B[a];
        int b = query(ai+1, r);
        int bi = B[b];
        ans[p++] = a;
        ans[p++] = b;
        if (ai != l) pq.insert(Seg(query(l, ai-1), l, ai-1));
        if (bi != r) pq.insert(Seg(query(bi+1, r), bi+1, r));
        if (ai + 1 != bi) pq.insert(Seg(query(ai+1, bi-1), ai+1, bi-1));
    }

    ans.map!(a => a.to!string).join(" ").writeln;
}


class SegmentTree {
    int[] table;
    int size;
    immutable int INF = 1 << 29;

    this(int n) {
        assert(bsr(n) < 29);
        size = 1 << (bsr(n) + 2);
        table = new int[](size);
        fill(table, INF);
    }

    void assign(int pos, int num) {
        return assign(pos, num, 0, 0, size/2-1);
    }

    void assign(int pos, int num, int i, int left, int right) {
        if (left == right) {
            table[i] = num;
            return;
        }
        auto mid = (left + right) / 2;
        if (pos <= mid)
            assign(pos, num, i*2+1, left, mid);
        else
            assign(pos, num, i*2+2, mid+1, right);
        table[i] = min(table[i * 2 + 1], table[i * 2 + 2]);
    }

    int query(int pl, int pr) {
        return query(pl, pr, 0, 0, size/2-1);
    }

    int query(int pl, int pr, int i, int left, int right) {
        if (pl > right || pr < left)
            return INF;
        else if (pl <= left && right <= pr)
            return table[i];
        else
            return
                min(query(pl, pr, i*2+1, left, (left+right)/2),
                    query(pl, pr, i*2+2, (left+right)/2+1, right));
    }
}