【校内训练2019-05-22】预言

【思路要点】

首先用 $Hall$ 定理 $+$ 线段树判断是否有解。若有解，考虑从前到后构造字典序最小的解。由于在 $pos$ 处填入一个数只会影响左端点为 $pos$ 的区间，可以二分出填入数字可能的最靠右的右端点 $rit$ ，填入数字的右端点需要在区间 $[pos,rit]$ 中。再用一棵线段树维护右端点在该区间中的数字的最小值即可。时间复杂度 $O(NLo{g}^{2}N)$ ，若改为线段树上二分，时间复杂度为 $O(NLogN)$ 。

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; const int INF = 1e9; typedef long long ll; typedef long double ld; typedef unsigned long long ull; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } struct MainSegmentTree { struct Node { int lc, rc; int Min, tag; } a[MAXN * 2]; int n, size, root; void update(int root) { a[root].Min = min(a[a[root].lc].Min, a[a[root].rc].Min); } void build(int &root, int l, int r) { root = ++size; a[root].Min = l; if (l == r) return; int mid = (l + r) / 2; build(a[root].lc, l, mid); build(a[root].rc, mid + 1, r); update(root); } void init(int x) { n = x; root = size = 0; build(root, 1, n); } void pushdown(int root) { if (a[root].tag) { a[a[root].lc].Min += a[root].tag; a[a[root].lc].tag += a[root].tag; a[a[root].rc].Min += a[root].tag; a[a[root].rc].tag += a[root].tag; a[root].tag = 0; } } void modify(int root, int l, int r, int ql, int qr, int d) { if (l == ql && r == qr) { a[root].Min += d; a[root].tag += d; return; } pushdown(root); int mid = (l + r) / 2; if (mid >= ql) modify(a[root].lc, l, mid, ql, min(qr, mid), d); if (mid + 1 <= qr) modify(a[root].rc, mid + 1, r, max(mid + 1, ql), qr, d); update(root); } void modify(int l, int r, int d) { if (l > r) return; else modify(root, 1, n, l, r, d); } int queryMin(int root, int l, int r, int ql, int qr) { if (l == ql && r == qr) return a[root].Min; pushdown(root); int mid = (l + r) / 2, ans = INF; if (mid >= ql) chkmin(ans, queryMin(a[root].lc, l, mid, ql, min(mid, qr))); if (mid + 1 <= qr) chkmin(ans, queryMin(a[root].rc, mid + 1, r, max(mid + 1, ql), qr)); return ans; } int queryMin(int l, int r) { if (l > r) return 0; else return queryMin(root, 1, n, l, r); } } MST; struct AuxSegmentTree { struct Node { int lc, rc; int Min; } a[MAXN * 2]; set <int> st[MAXN]; int n, size, root; void update(int root) { a[root].Min = min(a[a[root].lc].Min, a[a[root].rc].Min); } void build(int &root, int l, int r) { root = ++size; a[root].Min = INF; if (l == r) return; int mid = (l + r) / 2; build(a[root].lc, l, mid); build(a[root].rc, mid + 1, r); update(root); } void init(int x) { n = x; root = size = 0; build(root, 1, n); } void modify(int root, int l, int r, int x, int d) { if (l == r) { if (d >= 0) st[l].insert(d); else st[l].erase(-d); if (st[l].size()) a[root].Min = *st[l].begin(); else a[root].Min = INF; return; } int mid = (l + r) / 2; if (mid >= x) modify(a[root].lc, l, mid, x, d); else modify(a[root].rc, mid + 1, r, x, d); update(root); } void modify(int x, int d) { modify(root, 1, n, x, d); } int queryMin(int root, int l, int r, int ql, int qr) { if (l == ql && r == qr) return a[root].Min; int mid = (l + r) / 2, ans = INF; if (mid >= ql) chkmin(ans, queryMin(a[root].lc, l, mid, ql, min(mid, qr))); if (mid + 1 <= qr) chkmin(ans, queryMin(a[root].rc, mid + 1, r, max(mid + 1, ql), qr)); return ans; } int queryMin(int l, int r) { if (l > r) return 0; else return queryMin(root, 1, n, l, r); } } AST; int n, x[MAXN], y[MAXN]; void checkSolution() { static vector <int> a[MAXN]; for (int i = 1; i <= n; i++) a[x[i]].push_back(y[i]); MST.init(n); for (int i = n; i >= 1; i--) { for (auto x : a[i]) MST.modify(x, n, -1); int tmp = MST.queryMin(i, n); if (tmp - i + 1 < 0) { puts("-1"); exit(0); } } } int main() { freopen("prophesy.in", "r", stdin); freopen("prophesy.out", "w", stdout); read(n); for (int i = 1; i <= n; i++) read(x[i]), read(y[i]); checkSolution(); AST.init(n); static vector <int> a[MAXN]; for (int i = 1; i <= n; i++) a[x[i]].push_back(i); for (int i = 1; i <= n; i++) { for (auto x : a[i]) AST.modify(y[x], x); int l = i, r = n; while (l < r) { int mid = (l + r) / 2; if (MST.queryMin(i, mid) - i + 1 == 0) r = mid; else l = mid + 1; } int ans = AST.queryMin(i, l); printf("%d ", ans); AST.modify(y[ans], -ans); MST.modify(y[ans], n, 1); } return 0; }