Learning Algorithms

アルゴリズムの勉強メモ

Atcoder ARC 080 E. Young Maids

Atcoder ARC 080 E. Young Maids

E: Young Maids - AtCoder Regular Contest 080 | AtCoder

解法

ある区間(最初は全体)の数列の偶数番目($0-indexed$)の最小値と、その最小値より右側にあって、かつその数を基準に数えて、奇数番目にあるような数の最小値をとってくる、ということを繰り返せば題意の数列が求められる。
これらの数が位置$\ l\ $と$\ r\ $からとられたならば、次考える区間は、$\ [0, l),\ [l + 1, r),\ [r + 1, n)\ $である。これらを分割統治的にやっていくためには、キューを使えばよいが、次に取り出したい区間は、(その区間における偶数番目の数の最小値)が最小になるものであるから、そのように取り出せるように優先度付きキューを用意すればよい。さらに、区間の最小値を高速に求める必要があるので、当然セグメント木などを利用する。時間計算量は$O(n\log n)$。

実装
#include "bits/stdc++.h";
using namespace std;

#define OUT(x)  cerr << #x << " = " << x << endl;
#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
#define piii    pair<int, pair<int, int>>

static const int INF = 0x3f3f3f3f;

template<typename Type>
struct SegmentTree {
        vector<Type> data;
        int n;
        SegmentTree(int x) {
                n = pow(2, ceil(log2(x)));
                data.resize(2 * n - 1);
                for (int i = 0; i < 2 * n - 1; i ++) data[i] = mp(INF, i - n + 1) ; //初期値
        }
        Type merge(Type x, Type y) { //更新関数
                if (x.first < y.first) return x;
                else return y;
        }
        void update(int k, int p) { //k番目をpで更新する
                k += n - 1;
                data[k].first = p;
                while (k > 0) {
                        k = (k - 1) / 2;
                        data[k] = merge(data[k * 2 + 1], data[k * 2 + 2]);
                }
        }
        // [l, r)
        Type query(int a, int b) { return query(a, b, 0, 0, n); }
        Type query(int a, int b, int k, int l, int r) {
                if (r <= a || b <= l) return mp(INF, -1); //初期値
                if (a <= l && r <= b) return data[k];
                int m = (l + r) / 2;
                return merge(query(a, b, k * 2 + 1, l, m), query(a, b, k * 2 + 2, m, r));
        }
};
                                   
int main() {
        int i, j;
        int n;
        cin >> n;
        vector<int> p(n);
        for (i = 0; i < n; i ++) cin >> p[i];
        SegmentTree<pii> st_even(n), st_odd(n);
        for (i = 0; i < n; i ++) {
                if (i & 1) st_odd.update(i, p[i]);
                else st_even.update(i, p[i]);
        }
        priority_queue<piii, vector<piii>, greater<piii>> pq;
        pq.push(mp(st_even.query(0, n).first, mp(0, n)));
        vector<int> ans(n);
        int ansi = 0;
        while (!pq.empty()) {
                piii get = pq.top(); pq.pop();
                pii segment = get.second;
                int a, b;
                pii get1, get2;
                if (segment.first & 1) get1 = st_odd.query(segment.first, segment.second);
                else get1 = st_even.query(segment.first, segment.second);
                a = get1.second;
                ans[ansi ++] = get1.first;
                if (a & 1) get2 = st_even.query(a, segment.second);
                else get2 = st_odd.query(a, segment.second);
                b = get2.second;
                ans[ansi ++] = get2.first;
                if (segment.first < a) { 
                        if (segment.first & 1) pq.push(mp(st_odd.query(segment.first, a).first, mp(segment.first, a)));
                        else  pq.push(mp(st_even.query(segment.first, a).first, mp(segment.first, a)));
                }
                if (a + 1 < b) { 
                        if ((a + 1) & 1) pq.push(mp(st_odd.query(a + 1, b).first, mp(a + 1, b)));
                        else pq.push(mp(st_even.query(a + 1, b).first, mp(a + 1, b)));
                }
                if (b + 1 < segment.second) {
                        if ((b + 1) & 1) pq.push(mp(st_odd.query(b + 1, segment.second).first, mp(b + 1, segment.second)));
                        else pq.push(mp(st_even.query(b + 1, segment.second).first, mp(b + 1, segment.second)));
                }
        }
        for (i = 0; i < n; i ++) cout << ans[i] << (i == n - 1 ? '\n' : ' ');
        return 0;
}