一个有趣的题目【二分答案，2-SAT，线段树优化】

题目大意1

给定n(n≤2×104)个二元组(xi,yi)，要求从每个二元组中选择一个数构成集合S，最大化min{abs(i−j)|i,j∈S}。

分析与解

考场上最后1h想到正解…无奈以前并没有做过2-SAT，最后暴零滚粗…

首先显然二分答案ans，我们现在考虑如何验证。考虑如果我们选择了一个xi(或yi)，则∀k使得xk(yk)−xi(yi)<ans，必然不能选xk(yk)。选一个逻辑推出选另一个，于是可以用2-SAT解决这个问题。

然而2-SAT中的边数是O(n2)的，复杂度为O(n2lgW)，显然不能通过。考虑每一个节点只能影响其周围一段连续的区间，因此可以排序后用线段树将边数降到O(nlgn)，从而总的复杂度就是O(nlgnlgW)，就可以通过此题。

My_Code

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 130005;
struct TwoSat {
    struct node {
        int to, next;
    } edge[MAXN*120];
    int n, head[MAXN*4], top;
    inline int Not(int i)
    { return i <= n ? n+i : i-n; }
    void push(int i, int j)
    { ++top, edge[top] = (node){j, head[i]}, head[i] = top; }

    int dfn[MAXN*10], low[MAXN*10], stk[MAXN*10], stk_top, instk[MAXN*10];
    int gp[MAXN*10], gp_top, dfn_top;
    void init(int _n)
    {
        n = _n;
        memset(dfn, 0, sizeof dfn); memset(head, 0, sizeof head);
        memset(instk, 0, sizeof instk); memset(gp, 0, sizeof gp);
        gp_top = dfn_top = stk_top = top = 0;
    }

    void tarjan(int nd)
    {
        dfn[nd] = low[nd] = ++dfn_top, stk[++stk_top] = nd, instk[nd] = 1;
        for (int i = head[nd]; i; i = edge[i].next) {
            int to = edge[i].to;
            if (!dfn[to]) tarjan(to), low[nd] = min(low[nd], low[to]);
            else if (instk[to]) low[nd] = min(low[nd], dfn[to]);
        }
        if (dfn[nd] == low[nd]) {
            int now; ++gp_top;
            do {
                now = stk[stk_top--], gp[now] = gp_top, instk[now] = 0;
            } while (now != nd);
        }
    }

    bool work()
    {
        for (int i = 1; i <= n*2; i++)
            if (!dfn[i])
                tarjan(i);
        for (int i = 1; i <= n; i++)
            if (gp[i] == gp[i+n])
                return false;
        return true;
    }
} TSet;

struct pr {
    long long x;
    int from;
    friend bool operator < (const pr &a, const pr &b)
    {
        return a.x < b.x;
    }
} flag[MAXN];
int n, flg = 0;

int tree[(1<<18)+1], root = 0, N = 1<<17;
bool judge(long long k)
{
    TSet.init(n);
    for (int i = 1; i <= n*2; i++) TSet.push(n*2+i+N-1, TSet.Not(flag[i].from));
    for (int i = N-1; i >= 1; i--) {
        if (i*2 <= N-1+n*2) TSet.push(n*2+i, n*2+i*2); 
        if (i*2+1 <= N-1+n*2) TSet.push(n*2+i, n*2+i*2+1);
    }
    for (int i = 1; i <= n*2; i++) {
        int l = i+1, r = n*2;
        if (l <= r) {
            while (l <= r) {
                int mid = (l+r)>>1;
                if (flag[mid].x-flag[i].x < k) l = mid+1;
                else r = mid-1;
            }
            int j, k;
            if (i+1 <= l-1) {
                for (j = i+1+N-1, k = l-1+N-1; j < k; j >>= 1, k >>= 1) {
                    if (j&1) TSet.push(flag[i].from, n*2+j), j++;
                    if (!(k&1)) TSet.push(flag[i].from, n*2+k), k--;
                }
                if (j == k) TSet.push(flag[i].from, n*2+j);
            }
        }
        l = 1, r = i-1;
        if (l <= r) {
            while (l <= r) {
                int mid = (l+r)>>1;
                if (flag[i].x-flag[mid].x < k) r = mid-1;
                else l = mid+1;
            } 
            int j, k;
            if (r+1 <= i-1) {
                for (j = r+1+N-1, k = i-1+N-1; j < k; j >>= 1, k >>= 1) {
                    if (j&1) TSet.push(flag[i].from, n*2+j), j++;
                    if (!(k&1)) TSet.push(flag[i].from, n*2+k), k--;
                }
                if (j == k) TSet.push(flag[i].from, n*2+j);
            }
        }
    }
    return TSet.work();
}

int main()
{
    freopen("flag.in","r",stdin);
    freopen("flag.out","w",stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        long long a, b;
        scanf("%lld%lld", &a, &b);
        flag[++flg].x = a, flag[flg].from = i;
        flag[++flg].x = b, flag[flg].from = i+n;
    }
    sort(flag+1, flag+n*2+1);
    long long l = 0, r = 1e9;
    while (l <= r) {
        long long mid = (l+r)>>1;
        if (judge(mid)) l = mid+1;
        else r = mid-1;
    }
    cout << l-1 << endl;
    return 0;
}

出题人，VW ↩