[ARC069D] Flags

题目描述

思路

首先看到最小距离最大，果断二分答案。

然后问题就转化为第 $i$ 个标志可以放置在坐标 $x_i$ 或坐标 $y_i$ 上的最小距离是否可以比 $x$ 大。

这个问题是不是莫名熟悉，有一个变量有两种取值，并且有一定的约束关系（因为距离限制），然后找有没有可行解。于是你就想到了 2-SAT，然后开心的写了一发，TLE 了。

这里有一个问题，像这样连边的时间复杂度 $\Theta(n^2)$ 的，过不了最大的数据点，考虑优化。这时你需要用到一个 trick 叫做线段树优化建图。首先先对所有可能放旗子的点排序，然后你会发现一个点需要连的点是连续的。可以建一棵线段树，因为有父子关系，所有的父亲像儿子连边。为了方便写代码，我们可以强行要求叶子节点的下表为 $1 \sim 2n$ 。接下来就非常类似于区间询问了，直接递归就行了，总时间复杂度 $\Theta(n\log^2 n)$ 。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e4 * 5 + 10;

int Head[MAXN], Next[MAXN << 2], To[MAXN << 2], ToT;
void Add(int u, int v) {
    To[++ToT] = v;
    Next[ToT] = Head[u];
    Head[u] = ToT;
}

int Dfn[MAXN], Low[MAXN];
bool In_Stack[MAXN];
int Stack[MAXN], Top;
int Index, SCC, N;
int Belong[MAXN];

void Tarjan(int u) {
    Stack[++Top] = u;
    In_Stack[u] = true;
    Dfn[u] = Low[u] = ++Index;
    for (int i = Head[u]; i; i = Next[i]) {
        int v = To[i];
        if (!Dfn[v]) {
            Tarjan(v);
            Low[u] = min(Low[u], Low[v]);
        } else if (In_Stack[v]) {
            Low[u] = min(Low[u], Dfn[v]);
        }
    }

    if (Dfn[u] == Low[u]) {
        ++SCC;
        int v;
        do {
            v = Stack[Top--];
            Belong[v] = SCC;
            In_Stack[v] = false;
        } while (v != u);
    }
}

int GetOpposite(int x) {
    if (x <= N)
        return x + N;
    else
        return x - N;
}

pair<int, int> Flags[MAXN << 1];

int SegmentTree[MAXN << 2], Cnt;
void Build(int p, int l, int r) {
    SegmentTree[p] = ++Cnt;
    if (l == r) {
        Add(SegmentTree[p], GetOpposite(Flags[l].second));
        return;
    }
    int mid = l + r >> 1;
    Build(p << 1, l, mid);
    Build(p << 1 | 1, mid + 1, r);
    Add(SegmentTree[p], SegmentTree[p << 1]);
    Add(SegmentTree[p], SegmentTree[p << 1 | 1]);
}

void Link(int p, int L, int R, int l, int r, int x) {
    if (l > r) return;
    int mid = L + R >> 1;
    if (L == l && R == r)
    	Add(x, SegmentTree[p]);
    else if (r <= mid)
        Link(p << 1, L, mid, l, r, x);
    else if (l > mid)
        Link(p << 1 | 1, mid + 1, R, l, r, x);
    else {
        Link(p << 1, L, mid, l, mid, x);
        Link(p << 1 | 1, mid + 1, R, mid + 1, r, x);
    }
}

bool Check(int x) {
    ToT = Top = Index = SCC = 0;
    memset(Head, 0, sizeof Head);
    memset(Dfn, 0, sizeof Dfn);
    memset(Low, 0, sizeof Low);
    memset(In_Stack, 0, sizeof In_Stack);
    Build(1, 1, Cnt = 2 * N);
    for (int i = 1; i <= 2 * N; i++) {
        static int l, r;
        l = upper_bound(Flags + 1, Flags + 1 + 2 * N, make_pair(Flags[i].first - x, 0x3f3f3f3f)) - Flags;
        r = upper_bound(Flags + 1, Flags + 1 + 2 * N, make_pair(Flags[i].first + x - 1, 0x3f3f3f3f)) - Flags - 1;
        Link(1, 1, 2 * N, l, i - 1, Flags[i].second);
        Link(1, 1, 2 * N, i + 1, r, Flags[i].second);
    }
    for (int i = 1;
         i <= 2 * N; i++) {
        if (!Dfn[i]) Tarjan(i);
    }
    for (int i = 1; i <= N; i++) {
        if (Belong[i] == Belong[i + N]) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> Flags[i].first >> Flags[i + N].first;
        Flags[i].second = i;
        Flags[i + N].second = i + N;
    }

    sort(Flags + 1, Flags + 1 + 2 * N);

    int l = 0, r = Flags[2 * N].first - Flags[1].first + 1, mid, Ans = -1;

    while (l <= r) {
        mid = l + r >> 1;
        if (Check(mid)) {
            l = mid + 1;
            Ans = mid;
        } else {
            r = mid - 1;
        }
    }

    cout << Ans << endl;
    return 0;
}