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; }