APIO2018 题解

# windos 2024-05-05 09:35 0 21 来源：云博客

新家

首先这个没有修改只有询问，可以把年份当时间轴，按年份顺序模拟，这样我们就把年份这一维去掉了。

首先 $-1$ 比较好判断，单独记录一下目前存在几种商店就行，数组就行。

然后我们需要数据结构，支持：

插入和删除商店
查询不方便指数

考虑从 2 入手，对于一个查询二元组 $(l, y)$，对于每个类型 $i$，我们假设距离 $l$ 最近的这个类型的商店的坐标是 $x_i$，答案是 $\displaystyle \max_{i=1}^k(|x_t - l|)$，显然可以分类讨论为 ① $l <= x_t$，距离为 $x_t - l$ ② $x_t < l$，距离为 $l - x_t$。

那么我们就可以去掉绝对值，即在 $l$ 左/右边是最优决策，问题拆为 $\max(\max(l - x_t), \max(x_t‘ - l))$。注意这个 $x_t‘$ 是在 $l$ 右侧的 $x$。由于每个询问 $l$ 是确定的，所以对于前一部分，即最大化 $x_t$；对于后半部分，即最小化 $x‘_t$。

考虑在插入和删除商店时对每个位置最优决策的影响。

...然后发现这个最优性操作插入的时候无法确定答案，我自闭了...

无耻去看题解...

自己没想到二分答案emm。

我们考虑二分答案 $m$，那么如果 $ans > m$ ，等价于 $[l - m + 1, l + m - 1]$ 存在的不同类型商店数 $< k$，即在 $[l + m, \infty]$ 存在一个商店同类型的前驱的位置 $ \le l - m$，即他们的前驱最小值位置 $\le l - m$。这个前驱可以用 $\text{set}$ 进行维护，区间最小值用线段树维护，离散化一下，这样就能 $O(n \log 10^8 \log n)$ 了。

为了保证可行性的正确，所以我们还要在 $[n + 1, n + k]$ 分别插入位置为 $\infty$，颜色为 $1$ 到 $k$ 的 $k$ 种颜色，这样才能保证查后缀时，所有颜色都进行了统计。

代码

调了 5h ...

#include <iostream>#include <cstdio>#include <algorithm>#include <set>using namespace std;char buf[1 << 23], *p1 = buf, *p2 = buf;#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)void inline read(int &x) { x = 0; char s = getchar(); while (s > ‘9‘ || s < ‘0‘) s = getchar(); while (s >= ‘0‘ && s <= ‘9‘) x = (x << 1) + (x << 3) + s - ‘0‘, s = getchar();} typedef set<int>::iterator SIT;const int N = 300005, INF = 1e9;int n, k, q, pos[N * 2], tot, ans[N], cnt[N], num, len;struct Shop{ int x, y, t, w, id; bool operator < (const Shop &b) const { return t < b.t; }} s[N * 3];struct Loc{ int x, id; bool operator < (const Loc &b) const { return x < b.x; }} d[N * 2];set<int> c[N];struct Prob{ int l, t, id; bool operator < (const Prob &b) const { return t < b.t; }} e[N];int val[N << 3]; void inline pushup(int p) { val[p] = min(val[p << 1], val[p << 1 | 1]);}void build(int p, int l, int r) { val[p] = INF; if (l == r) return; int mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);}void change(int p, int l, int r, int x, int k) { if (l == r) { val[p] = k; return; } int mid = (l + r) >> 1; if (x <= mid) change(p << 1, l, mid, x, k); else change(p << 1 | 1, mid + 1, r, x, k); pushup(p);}int query(int p, int l, int r, int x, int y) { if (x <= l && r <= y) return val[p]; int mid = (l + r) >> 1, res = INF; if (x <= mid) res = min(res, query(p << 1, l, mid, x, y)); if (mid < y) res = min(res, query(p << 1 | 1, mid + 1, r, x, y)); return res;}// 插入 Shop s[i]void inline ins(int i) { int p = pos[s[i].id], col = s[i].y; if (s[i].w) { if (!cnt[col]) num++; cnt[col]++; } SIT it = c[col].lower_bound(p); if (it != c[col].end()) { change(1, 1, n + k, *it, s[i].x); } if (it != c[col].begin()) { it--; change(1, 1, n + k, p, d[*it].x); } else change(1, 1, n + k, p, -INF); c[col].insert(p);}// 删除 Shop s[i]void inline del(int i) { int p = pos[s[i].id], col = s[i].y; --cnt[col]; if (!cnt[col]) num--; SIT it = c[col].lower_bound(p), jt = it; change(1, 1, n + k, p, INF); if (jt != c[col].end() && jt != c[col].begin()) { ++jt; int R = *jt; --jt; --jt; int L = *jt; change(1, 1, n + k, R, d[L].x); } else if (jt != c[col].end()) { ++jt; int R = *jt; change(1, 1, n + k, R, -INF); } c[col].erase(it); }bool inline check(int mid, int i) { int R = upper_bound(d + 1, d + 1 + len, (Loc) { e[i].l + mid, 0 } ) - d; return query(1, 1, n + k, R, n + k) >= e[i].l - mid;}int main() { read(n); read(k); read(q); build(1, 1, n + k); for (int i = 1; i <= n; i++) { int x, y, a, b; read(x); read(y); read(a); read(b); d[++len] = (Loc) { x, i }; s[++tot] = (Shop) { x, y, a, 1, i }; s[++tot] = (Shop) { x, y, b + 1, -1, i }; } for (int i = 1; i <= k; i++) { s[++tot] = (Shop) { INF, i, 1, 0, n + i }; d[++len] = (Loc) { INF, n + i }; } sort(d + 1, d + 1 + len); sort(s + 1, s + 1 + tot); for (int i = 1; i <= len; i++) pos[d[i].id] = i; for (int i = 1; i <= q; i++) read(e[i].l), read(e[i].t), e[i].id = i; sort(e + 1, e + 1 + q); for (int i = 1, j = 1; i <= q; i++) { while (j <= tot && s[j].t <= e[i].t) { if (s[j].w >= 0) ins(j); else del(j); ++j; } if (num < k) { ans[e[i].id] = -1; continue; } int l = 0, r = INF; while (l < r) { int mid = (l + r) >> 1; if (check(mid, i)) r = mid; else l = mid + 1; } ans[e[i].id] = r; } for (int i = 1; i <= q; i++) printf("%d\n", ans[i]); return 0;}

还可以进一步优化，考虑在线段树上二分，设那个不合法位置为 $y$，记 $[y, \infty)$ 中最小的前驱为 $pre$，即求最大的 $y$ 满足 $y + pre \le 2x$，答案就是 $y - l$，那么在线段树上维护 $pre$ 的最小值，显然 $pre + y$ 是一个递增的形式，所以如果令 $1$ 代表满足该式子， $0$ 代表不符合，组成的序列一定是 $1111100000$ 状物的，具有单调性，这样我们把最大的 $1$ 找出来，答案就在 $1$ 这个位置。

假设当前枚举到线段树上的 $[l, r]$。

如果 $x$ 在 $[l, mid]$，判断一下 $mid + 1$ 有没有满足上述不等式的，有就去右边，否则去左边
如果 $x$ 在 $[mid + 1, r]$，直接去右边查即可。

这样就能 $O(n \log n)$ 了。

代码

细节太多了，我自闭了，调了七个多小时。你谷 Rank 1 可还行。

离散化后，假设 $d_i$ 代表 $i$ 的坐标，上面一步要查 $d_{mid} + 1$ 而非 $d_{mid + 1}$！因为整数域上，$(d_{mid}, d_{mid+1})$ 也有可能的答案，如果这中间有满足不合法式子，那么一定要去右边，因为这样才能摆脱 $pre_{mid}$ 的影响，这个毒瘤死了，我查了三个小时。

#include <iostream>#include <cstdio>#include <algorithm>#include <set>using namespace std;char buf[1<<23], *p1=buf, *p2=buf, obuf[1<<23], *O=obuf;#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<21, stdin), p1 == p2) ? EOF : *p1++)void inline read(int &x) { x = 0; char s = getchar(); while (s > ‘9‘ || s < ‘0‘) s = getchar(); while (s >= ‘0‘ && s <= ‘9‘) x = (x << 1) + (x << 3) + s - ‘0‘, s = getchar();} typedef set<int>::iterator SIT;const int N = 300005, INF = 1e9;int n, k, q, pos[N * 2], tot, ans[N], cnt[N], num, len;struct Shop{ int x, y, t, w, id; bool operator < (const Shop &b) const { return t < b.t; }} s[N * 3];struct Loc{ int x, id; bool operator < (const Loc &b) const { return x < b.x; }} d[N * 2];set<int> c[N];struct Prob{ int l, t, id; bool operator < (const Prob &b) const { return t < b.t; }} e[N];int val[N << 3]; void inline pushup(int p) { val[p] = min(val[p << 1], val[p << 1 | 1]);}void build(int p, int l, int r) { val[p] = INF; if (l == r) return; int mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);}void change(int p, int l, int r, int x, int k) { if (l == r) { val[p] = k; return; } int mid = (l + r) >> 1; if (x <= mid) change(p << 1, l, mid, x, k); else change(p << 1 | 1, mid + 1, r, x, k); pushup(p);}int queryV(int p, int l, int r, int x, int y) { if (x <= l && r <= y) return val[p]; int mid = (l + r) >> 1, res = 2 * INF; if (x <= mid) res = min(res, queryV(p << 1, l, mid, x, y)); if (mid < y) res = min(res, queryV(p << 1 | 1, mid + 1, r, x, y)); return res;}int query(int p, int l, int r, int x, int v) { if (l == r) { return min(d[r].x - x, x - queryV(1, 1, n + k, r, n + k)); } int mid = (l + r) >> 1; if (x > d[mid].x) return query(p << 1 | 1, mid + 1, r, x, v); else { if (d[mid].x + 1 + min(v, val[p << 1 | 1]) <= 2 * x) return query(p << 1 | 1, mid + 1, r, x, v); else return query(p << 1, l, mid, x, min(v, val[p << 1 | 1])); }}// 插入 Shop s[i]void inline ins(int i) { int p = pos[s[i].id], col = s[i].y; if (s[i].w) { if (!cnt[col]) num++; cnt[col]++; } SIT it = c[col].lower_bound(p); if (it != c[col].end()) { change(1, 1, n + k, *it, s[i].x); } if (it != c[col].begin()) { it--; change(1, 1, n + k, p, d[*it].x); } else change(1, 1, n + k, p, - INF); c[col].insert(p);}// 删除 Shop s[i]void inline del(int i) { int p = pos[s[i].id], col = s[i].y; --cnt[col]; if (!cnt[col]) num--; SIT it = c[col].lower_bound(p), jt = it; change(1, 1, n + k, p, INF); if (jt != c[col].end() && jt != c[col].begin()) { ++jt; int R = *jt; --jt; --jt; int L = *jt; change(1, 1, n + k, R, d[L].x); } else if (jt != c[col].end()) { ++jt; int R = *jt; change(1, 1, n + k, R, -INF); } c[col].erase(it); }int main() { read(n); read(k); read(q); build(1, 1, n + k); for (int i = 1; i <= n; i++) { int x, y, a, b; read(x); read(y); read(a); read(b); d[++len] = (Loc) { x, i }; s[++tot] = (Shop) { x, y, a, 1, i }; s[++tot] = (Shop) { x, y, b + 1, -1, i }; } for (int i = 1; i <= k; i++) { s[++tot] = (Shop) { INF, i, 1, 0, n + i }; d[++len] = (Loc) { INF, n + i }; } sort(d + 1, d + 1 + len); sort(s + 1, s + 1 + tot); for (int i = 1; i <= len; i++) pos[d[i].id] = i; for (int i = 1; i <= q; i++) read(e[i].l), read(e[i].t), e[i].id = i; sort(e + 1, e + 1 + q); for (int i = 1, j = 1; i <= q; i++) { while (j <= tot && s[j].t <= e[i].t) { if (s[j].w >= 0) ins(j); else del(j); ++j; } if (num < k) { ans[e[i].id] = -1; continue; } ans[e[i].id] = query(1, 1, n + k, e[i].l, INF); } for (int i = 1; i <= q; i++) printf("%d\n", ans[i]); return 0;}