题解 AT2336 【Flags】

· · 题解

二分答案，并用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与区间内点都联通）

代码：

#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);
}