http://arc080.contest.atcoder.jp/tasks/arc080_c
逆から見ると、列の偶数番目と奇数番目をとって、3つの列に分割して再帰的にまた同じようなことをする問題に言い換えられる。
しかしうまく実装する方法が思いつかず、ひたすらデバッガ使って通した。強い人のコードを参考にします。
int N; int A[MAX_N]; vector<int> G[MAX_N * 3]; pi P[MAX_N * 3]; int E; segtree os, es; void dfs(int l, int r, int k, bool odd) { assert(k == E); int a = l / 2, b, c, d = r / 2; pi fp, sp; if(!odd) { fp = es.get(a, d); b = fp.sec; sp = os.get(b, d); c = sp.sec; if(b == -1 || c == -1) { P[k] = T().v; return; } es.update(b, T()); os.update(c, T()); a *= 2; d *= 2; b *= 2; c = c * 2 + 2; } else { fp = os.get(a, d); b = fp.sec; sp = es.get(b + 1, d); c = sp.sec; if(b == -1 || c == -1) { P[k] = T().v; return; } os.update(b, T()); es.update(c, T()); a *= 2; d *= 2; b = b * 2 + 2; c *= 2; } P[E] = pi(fp.fst, sp.fst); if(a != b) { E++; G[k].push_back(E); dfs(a, b, E, odd); } if(b != c) { E++; G[k].push_back(E); dfs(b, c, E, 1 ^ odd); } if(c != d) { E++; G[k].push_back(E); dfs(c, d, E, odd); } } pi ans[MAX_N]; void solve() { cin >> N; os.init(N / 2); es.init(N / 2); rep(i, 0, N) { cin >> A[i]; if(i % 2 == 0) es.update(i / 2, pi(A[i], i / 2)); else os.update(i / 2, pi(A[i], i / 2)); } dfs(0, N, 0, false); int M = 0; priority_queue<ppi, vector<ppi>, greater<ppi> > que; que.push(make_pair(P[0], 0)); while(!que.empty()) { ppi pp = que.top(); que.pop(); //debug(M, pp.fst); ans[M++] = pp.fst; int v = pp.sec; rep(i, 0, (int)G[v].size()) { if(P[G[v][i]] != T().v) { que.push(make_pair(P[G[v][i]], G[v][i])); } } } rep(i, 0, M) { cout << ans[i].fst << " " << ans[i].sec << " "; } cout << "\n"; }
(8/27追記)N/2ではなくN要素のsegtree(間はinfで埋める)でやれば実装簡単。