ARC165F Make Adjacent

D1a5y。

记录 \(x(1\le x\le n)\) 出现位置分别为 \(l_x,r_x(l_x< r_x)\)，讨论一下发现当两个数 \(x,y\) 满足 \(l_x<l_y,r_x<r_y\) 时操作后 \(x\) 一定出现在 \(y\) 前面，不然可以交换位置以达到更优步数。否则发现无论怎么操作发现都不影响答案。

所以我们将 \(x\) 描述为平面上的点 \((l_x,r_x)\)，操作为依次在平面上选择一个点删去，且需要满足删去的点左下角没有还没被删的点。直接建图，将 \((l_x,r_x)\) 向所有 \((l_y,r_y),l_x<l_y,r_x<r_y\) 连边，跑字典序最小拓扑序就是最优解。

但是这样边数是 \(O(n^2)\) 的，注意到点数 \(O(n)\)，考虑优化建图。

按照 \(l_x\) 从大到小扫描线，每次相当于对于一个 \(r_i\) 排序后的后缀连边。这样的连边是一段区间，可以线段树优化建图，线段树建立在 \(r\) 序列上。

但是 \(l_x\) 向左移动时会插入新的 \(r_x\)，为了让上一时刻的连边不包含新插入的 \(r_x\)，需要可持久化。

复杂度 \(O(n\log n)\)。

// Problem: F - Make Adjacent
// Contest: AtCoder - AtCoder Regular Contest 165
// URL: https://atcoder.jp/contests/arc165/tasks/arc165_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

namespace vbzIO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
    #if ONLINE_JUDGE
    #define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
    #else
    #define gh() getchar()
    #endif
    #define mt make_tuple
    #define mp make_pair
    #define fi first
    #define se second
    #define pc putchar
    #define pb emplace_back
    #define ins insert
    #define era erase
    typedef tuple<int, int, int> tu3;
    typedef pair<int, int> pi;
    inline int rd() {
        char ch = gh();
        int x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    inline void wr(int x) {
        if (x < 0) x = ~(x - 1), putchar('-');
        if (x > 9) wr(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace vbzIO;

const int N = 4e5 + 400;

pi p[N];
int n, tot, rt, a[N], in[N << 5], rp[N];
vector<int> g[N << 5], ans;

struct seg { int lc, rc; } tr[N << 5];

#define ls tr[x].lc
#define rs tr[x].rc
#define mid ((l + r) >> 1)

void add_edge(int u, int v) { if (u && v) g[u].pb(v), in[v]++; }
void add(int l, int r, int p, int q, int y, int &x) {
	tr[x = ++tot] = tr[y];
	if (l == r) return add_edge(x, q);
	if (p <= mid) add(l, mid, p, q, tr[y].lc, ls);
	else add(mid + 1, r, p, q, tr[y].rc, rs);
	add_edge(x, ls), add_edge(x, rs);
}

void upd(int l, int r, int s, int t, int p, int x) {
	if (!x) return;
	if (s <= l && r <= t) return add_edge(p, x);
	if (s <= mid) upd(l, mid, s, t, p, ls);
	if (t > mid) upd(mid + 1, r, s, t, p, rs);
}

priority_queue<pi, vector<pi>, greater<pi> > q;

void topo() {
	for (int i = 1; i <= tot; i++)
		if (!in[i]) q.push(mp((i <= n ? i : 0), i));
	while (!q.empty()) {
		pi p = q.top(); q.pop();
		int u = p.se;
		if (u <= n) ans.pb(u);
		for (int v : g[u]) {
			in[v]--;
			if (!in[v]) q.push(mp((v <= n ? v : 0), v));
		}
	}
}

int main() {
	n = tot = rd();
	for (int i = 1; i <= (n << 1); i++) {
		a[i] = rd();
		if (!p[a[i]].fi) p[a[i]].fi = i;
		else p[a[i]].se = i;
	}
	for (int i = 1; i <= n; i++) rp[p[i].fi] = p[i].se;
	for (int i = (n << 1); i; i--) {
		if (!rp[i]) continue;
		upd(1, (n << 1), rp[i], (n << 1), a[i], rt);
		add(1, (n << 1), rp[i], a[i], rt, rt);
	}
	topo();
	for (int i : ans) 
		wr(i), pc(' '), wr(i), pc(' ');
	return 0;
}