题解 AT2336 【Flags】
w1049
2019-10-29 23:32:32
二分答案，并用2-sat判定。
大致思路：
1. 二分一个距离mid，作为最大距离。
2. 判断是否可以让每个旗子之间的距离都小于等于mid。如果可以，更新答案，尝试增大mid；如果不可以，缩小mid并重新判断。
本题最大范围如果$O(n^2)$建边是无法通过的，由于每次都是向左右一个区间内建边，所以用线段树辅助建图。
用$x_i$表示旗帜$i$的一个位置，对应的另一个位置为$x'_i$，那么我们需要建的边就是$x_i->\{x'_j||x_i-x_j|>mid\}$（此处的$x_j$可以是题中的$x$，也可以是题中的$y$）。
可以看出，从$x_i$到左右$mid$范围内需要建边。
因此，我们将题中$x$、$y$放在一起排序，并在此之上建立一颗线段树。
有几种不同的方式可以实现这一目的，我采用的是以下这种：
对于排序后的每个点建立一个“占位符”作为线段树的叶子，由占位符向对立的点离岸边；线段树中父亲向儿子连边。
这样，向一个范围内的对立点连边就转换成了线段树上的区间操作。
可以看图：
建出的线段树：
由$x_2$向蓝色线标注区间内连边：
（红色为实际连边，粉色为达到的效果，即：使得$x_2$与区间内点都联通）
代码：
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define clear(x) memset(x, 0, sizeof(x))
#define op(x) ((x) <= n ? (x) + n : (x) - n)
// op可以求出一个点x的对立点
#define mid ((l + r) / 2)
#define ls now * 2
#define rs now * 2 + 1
const int N = 4e4 + 10, M = N * 20;
int hd[N * 5], nxt[M], t[M], ec;
void addEdge(int u, int v) {
t[++ec] = v;
nxt[ec] = hd[u];
hd[u] = ec;
}
struct Flag {
int pos, id;
bool operator<(const Flag& f) const { return pos < f.pos; }
Flag(int pos = 0): pos(pos) {}
} flgs[N * 2];
int n;
int cnt;
int id[N * 5];
void build(int now, int l, int r) {
id[now] = ++cnt;
if (l == r) {
addEdge(id[now], op(flgs[l].id));
// 由“占位符”向真实点的对立点连边
return;
}
build(ls, l, mid);
build(rs, mid + 1, r);
addEdge(id[now], id[ls]);
addEdge(id[now], id[rs]);
// 由父亲向儿子连边
}
void link(int now, int l, int r, int x, int y, int point) {
// 由point向区间[x,y]连边
if (y < x) return;
if (l == x && y == r) addEdge(point, id[now]);
else if (y <= mid) link(ls, l, mid, x, y, point);
else if(x > mid) link(rs, mid + 1, r, x, y, point);
else link(ls, l, mid, x, mid, point), link(rs, mid + 1, r, mid + 1, y, point);
}
#undef mid
int dfn[N * 5], low[N * 5], tim;
int stk[N * 5], tp;
int scc[N * 5], sc;
bool in[N * 5];
void dfs(int u) { // Tarjan算法 强连通分量
in[u] = 1;
dfn[u] = low[u] = ++tim;
stk[++tp] = u;
int v;
for (int i = hd[u]; i; i = nxt[i]) {
if (!dfn[v = t[i]]) dfs(v), low[u] = min(low[u], low[v]);
else if (in[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
++sc;
do {
scc[v = stk[tp--]] = sc;
in[v] = 0;
} while (v != u);
}
}
bool check(int v) {
tp = tim = ec = 0;
clear(hd), clear(dfn), clear(low);
build(1, 1, cnt = 2 * n);
int l, r;
for (int i = 1; i <= 2 * n; i++) {
l = upper_bound(flgs + 1, flgs + 1 + 2 * n, Flag(flgs[i].pos - v)) - flgs;
r = upper_bound(flgs + 1, flgs + 1 + 2 * n, Flag(flgs[i].pos + v - 1)) - flgs - 1;
link(1, 1, 2 * n, l, i - 1, flgs[i].id), link(1, 1, 2 * n, i + 1, r, flgs[i].id);
}
for (int i = 1; i <= 2 * n; i++) if (!dfn[i]) dfs(i);
for (int i = 1; i <= n; i++) if(scc[i] == scc[i + n]) return 0;
// 判断x与y是否在同一个强连通分量内
return 1;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &flgs[i].pos, &flgs[i + n].pos);
flgs[i].id = i, flgs[i + n].id = i + n;
}
sort(flgs + 1, flgs + n * 2 + 1);
int l = 0, r = flgs[2 * n].pos - flgs[1].pos + 1, mid, ans;
while (l <= r) { // 二分
mid = (l + r) / 2;
if (check(mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
printf("%d", ans);
}
```