跳转至

AT_arc069_d [ARC069F] Flags 题解

你有 \(n\) 个旗子，第 \(i\) 个旗子可以插在数轴的 \(x_i\) 或 \(y_i\) 位置处。请你最大化两个旗子之间的最近距离，输出最大值即可。

\(n\le 10^4,\ 1\le x_i,y_i\le 10^9\)

首先二分答案，问题转化为：要求任意两个旗子都至少距离 \(mid\) 长度，问是否可行。注意到这是一个 2-SAT 问题，但是边数很多，因此使用线段树优化建图即可。

注意：由于不能向自己连边，因此线段树必须维护排好序的序列，而不是（离散化后的）值域。

AC 代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include<iostream>
#include<algorithm>
using namespace std;
const int N1 = 1e4 + 10;
const int N2 = 2e4 + 10;
const int LOGN = 15;
const int V = 2e4;
const int N = 8 * V + N2;
const int M = 8 * V + 2 * N2 + 2 * N2 * 2 * LOGN;

struct Edge {
    int v, next;
} pool[M];
int ne, head[N];
int prene, prehead[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

void save() {
    for(int i = 0; i < N; i++) prehead[i] = head[i];
    prene = ne;
}

void load() {
    for(int i = 0; i < N; i++) head[i] = prehead[i];
    ne = prene;
}

int n;
int a[N1][2];

int chd[8 * N2][2];

int num2[N2], cnt[N2], num[N2], inv[N2];
void lisanhua() {
    for(int i = 1; i <= n; i++) num2[i] = a[i][0];
    for(int i = 1; i <= n; i++) num2[i + n] = a[i][1];
    sort(num2 + 1, num2 + 1 + 2 * n);
    for(int i = 1; i <= n; i++) {
        int tmp = a[i][0];
        a[i][0] = lower_bound(num2 + 1, num2 + 1 + 2 * n, tmp) - num2;
        a[i][0] += cnt[a[i][0]]++;
        num[a[i][0]] = tmp;
    }
    for(int i = 1; i <= n; i++) {
        int tmp = a[i][1];
        a[i][1] = lower_bound(num2 + 1, num2 + 1 + 2 * n, tmp) - num2;
        a[i][1] += cnt[a[i][1]]++;
        num[a[i][1]] = tmp;
    }
    for(int i = 1; i <= n; i++) inv[a[i][0]] = a[i][1];
    for(int i = 1; i <= n; i++) inv[a[i][1]] = a[i][0];
}

int nn;
void build(int p, int l, int r, int tp) {
    if(l == r) {
        if(tp == 0) addEdge(p, 8 * V + inv[l]);
        else addEdge(8 * V + l, p);
        return;
    }
    int mid = (l + r) >> 1;
    chd[p][0] = ++nn; build(chd[p][0], l, mid, tp);
    chd[p][1] = ++nn; build(chd[p][1], mid + 1, r, tp);
    if(tp == 0) {
        addEdge(p, chd[p][0]);
        addEdge(p, chd[p][1]);
    } else {
        addEdge(chd[p][0], p);
        addEdge(chd[p][1], p);
    }
}

void addEdge_Range(int p, int l, int r, int ql, int qr, int s, int tp) {
    if(ql > qr) return;
    if(ql <= l && r <= qr) {
        if(tp == 0) addEdge(s, p);
        else addEdge(p, s);
        return;
    }
    int mid = (l + r) >> 1;
    if(ql <= mid) addEdge_Range(chd[p][0], l, mid, ql, qr, s, tp);
    if(mid < qr) addEdge_Range(chd[p][1], mid + 1, r, ql, qr, s, tp);
}

namespace tarjan {
    int n;
    int dfn[N], low[N], dt;
    int col[N], bccCnt, sta[N], top;
    void clear() {
        for(int i = 1; i <= n; i++) dfn[i] = low[i] = col[i] = 0;
        dt = top = bccCnt = 0;
    }
    void dfs(int u) {
        low[u] = dfn[u] = ++dt;
        sta[++top] = u;
        for(int e = head[u]; e; e = pool[e].next) {
            int v = pool[e].v;
            if(!dfn[v]) {
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else if(!col[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }
        if(dfn[u] == low[u]) {
            ++bccCnt;
            while(sta[top + 1] != u) {
                col[sta[top]] = bccCnt;
                --top;
            }
        }
    }
    void run() {
        for(int i = 1; i <= n; i++) {
            if(!dfn[i]) dfs(i);
        }
    }
}

using tarjan::col;

bool check(int mid) {
    load();
    for(int i = 1; i <= n; i++) {
        int tl = lower_bound(num + 1, num + 1 + 2 * n, num[a[i][0]] - mid + 1) - num;
        addEdge_Range(1, 1, 2 * n, tl, a[i][0] - 1, 8 * V + a[i][0], 0);
        addEdge_Range(4 * V + 1, 1, 2 * n, tl, a[i][0] - 1, 8 * V + a[i][1], 1);
    }
    for(int i = 1; i <= n; i++) {
        int tl = lower_bound(num + 1, num + 1 + 2 * n, num[a[i][1]] - mid + 1) - num;
        addEdge_Range(1, 1, 2 * n, tl, a[i][1] - 1, 8 * V + a[i][1], 0);
        addEdge_Range(4 * V + 1, 1, 2 * n, tl, a[i][1] - 1, 8 * V + a[i][0], 1);
    }
    tarjan::clear();
    tarjan::run();
    for(int i = 1; i <= n; i++) {
        if(col[8 * V + a[i][0]] == col[8 * V + a[i][1]]) return false;
    }
    return true;
}

int main() {

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i][0] >> a[i][1];

    lisanhua();

    nn = 1; build(1, 1, 2 * n, 0);
    nn = 4 * V + 1; build(4 * V + 1, 1, 2 * n, 1);
    save();

    tarjan::n = 8 * V + 2 * n;

    int l = 0, r = 1e9 + 10;
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        if(check(mid)) {
            l = mid;
        } else r = mid - 1;
    }

    cout << l << '\n';

    return 0;
}