AT_arc069_d [ARC069F] Flags 做题记录

· · 个人记录

一道相当好且难做的题，让我学习到了线段树优化建图。

我们发现，设二分值为 k，只要点 j 的 x_j 值或 y_j 值在点 i 的 x_i 值或 y_i 值处，那么 i 就会向这个值表示的 j 拆出的点的反点（好像这是正规的说法）连边，也就是 x_j 满足条件像 j+n 连边，y_j 同理。

那么我们发现，连边数会非常巨大，点数也有 1e4，如果用 O(n^2) 那就会爆炸，而且链式前向星撑不到 T，她会 RE（没错是她^_^），而 vector 就会 T 和 M。那怎么办？我们发现，这是一个区间的连边，那假如我们一口气把一个区间的边都连上呢？

这就是线段树优化建边，我们先建一棵线段树，不需要什么表示区间的 l 和 r，只需要一个数组 id 表示这个点的编号，然后建树：

void build(int u, int l, int r)
{
    id[u] = ++tot;
    if (l == r)
        return add(id[u], a[l].id <= n ? a[l].id + n : a[l].id - n);
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    add(id[u], id[u << 1]);
    add(id[u], id[u << 1 | 1]);
}

然后我们会有很多疑问，这【数据删除】地是在干嘛？首先看到这一句 add(id[u], a[l].id <= n ? a[l].id + n : a[l].id - n);。我们要先说明这棵线段树存的是什么，它存的是由小到大的坐标值，就是 x 和 y 了。我们先把点拆开，用结构体（或 pair）储存，储存两个信息：此点的值和点的编号，belike：

struct node
{
    int x, id;
    node(int xs = 0)
    {
        x = xs;
    }
    bool operator <(const node &o)const
    {
        return x < o.x;
    }
} a[N];
for (rnt i = 1; i <= n; i++)
        a[i].x = read(), a[i + n].x = read(), a[i].id = i, a[i + n].id = i + n;
sort(a + 1, a + 2 * n + 1);

那么每个叶子节点就代表着一个点，且叶子结点从左到右就是节点值从小到大，那么在非叶子节点，我们建边连向两个儿子；在叶子节点，我们连向这个叶子节点代表的点的反点，为什么？我们可以想到。如果这个叶子节点代表着点 i，当它的 x_i 在点 j 的 x_j 或 y_j 正负 k 范围内，那么 j 就会连向 i+n 代表 i 选 y_i 值。这里拆点 i 表示选择 x_i，i+n 代表选 y_i，不会不知道吧？（别到时候把我回旋镖了）。

那么线段树建好了每个点该怎么连呢？我们知道一个点连自己的反点相当与排除这个点，所以不拿来排除答案就不能连。我们要连的是枚举到的点值 a（由于拆点，所以要枚举 2n 个点，用 x 或 y 可能有歧义），寻找比 a 小 k 的第一个数，寻找比 a 大或等于 k 的第一个数前一个数（注意等于不需要建边），然后线段树区间建边，belike：

void modify(int u, int l, int r, int x, int y, int k)
{
    if (x > r || y < l)
        return;
    if (x <= l && r <= y)
        return add(k, id[u]);
    int mid = (l + r) >> 1;
    modify(u << 1, l, mid, x, y, k);
    modify(u << 1 | 1, mid + 1, r, x, y, k);
}

省略

tot = 2 * n;//不设置初值会出事
build(1, 1, 2 * n);//记得先建树
for (rnt i = 1; i <= 2 * n; i++)
    {
        int x = upper_bound(a + 1, a + 2 * n + 1, node(a[i].x - k)) - a;
        int y = lower_bound(a + 1, a + 2 * n + 1, node(a[i].x + k)) - a - 1;
        modify(1, 1, 2 * n, x, i - 1, a[i].id);
        modify(1, 1, 2 * n, i + 1, y, a[i].id);
    }

我们发现，区间建边分成了两部分，避开了连向自己反点的行为，当找到被区间包含的线段树点时，就从当前枚举点的 id 连一条边到当前线段树点，正确性可想而知。

剩下的就是二分区间、tarjan，判断，输出就行了，记得每次二分都要清空。
还有，数组开大点，链式前向星可以完成这道题的（^_^）。
代码：

//Just Sayori
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
#define rnt register int
#define gr getchar
#define pr putchar
#define N 500005
#define M 1000000007
using namespace std;

inline ll read()
{
    ll x = 0, f = 1;
    char ch = gr();
    while (ch < '0' || ch > '9')
        ch == '-' ? f = -1, ch = gr() : ch = gr();
    while (ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = gr();
    return x * f;
}

inline void write(ll x)
{
    static int top = 0, sta[39];
    if (x < 0)
        pr('-');
    do
        sta[++top] = x % 10, x /= 10;
    while (x);
    while (top)
        pr(sta[top--] ^ 48);
}

struct edge
{
    int v, next;
} e[N << 3];
int head[N], cnt;

inline void add(int u, int v)
{
    e[++cnt] = {v, head[u]}, head[u] = cnt;
}
int n, m, ans, bcc, top, tot;
int id[N << 2], dfn[N], low[N], num[N], vis[N], ord[N], stack[N];

struct node
{
    int x, id;
    node(int xs = 0)
    {
        x = xs;
    }
    bool operator <(const node &o)const
    {
        return x < o.x;
    }
} a[N];

void tarjan(int u)
{
    dfn[u] = low[u] = ++cnt;
    vis[u] = 1, stack[++top] = u;
    for (rnt i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v;
        if (!dfn[v])
            tarjan(v), low[u] = min(low[u], low[v]);
        else if (vis[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        bcc++;
        while (stack[top + 1] != u)
            num[stack[top]] = bcc, vis[stack[top--]] = 0;
    }
}

void build(int u, int l, int r)
{
    id[u] = ++tot;
    if (l == r)
        return add(id[u], a[l].id <= n ? a[l].id + n : a[l].id - n);
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    add(id[u], id[u << 1]);
    add(id[u], id[u << 1 | 1]);
}

void modify(int u, int l, int r, int x, int y, int k)
{
    if (x > r || y < l)
        return;
    if (x <= l && r <= y)
        return add(k, id[u]);
    int mid = (l + r) >> 1;
    modify(u << 1, l, mid, x, y, k);
    modify(u << 1 | 1, mid + 1, r, x, y, k);
}

bool work(int k)
{
    for (rnt i = 1; i <= tot; i++)
        dfn[i] = num[i] = vis[i] = head[i] = stack[i] = 0;
    bcc = cnt = top = 0, tot = 2 * n;
    build(1, 1, 2 * n);
    for (rnt i = 1; i <= 2 * n; i++)
    {
        int x = upper_bound(a + 1, a + 2 * n + 1, node(a[i].x - k)) - a;
        int y = lower_bound(a + 1, a + 2 * n + 1, node(a[i].x + k)) - a - 1;
        modify(1, 1, 2 * n, x, i - 1, a[i].id);
        modify(1, 1, 2 * n, i + 1, y, a[i].id);
    }
    cnt = 0;
    for (rnt i = 1; i <= 2 * n; i++)
        if (!dfn[i])
            tarjan(i);
    for (rnt i = 1; i <= n; i++)
        if (num[i] == num[i + n])
            return 0;
    return 1;
}

int main()
{
    n = read();
    for (rnt i = 1; i <= n; i++)
        a[i].x = read(), a[i + n].x = read(), a[i].id = i, a[i + n].id = i + n;
    sort(a + 1, a + 2 * n + 1);
    int l = 0, r = a[2 * n].x - a[1].x + 1;
    while (l < r)
    {
        int mid = (l + r + 1) >> 1;
        if (work(mid))
            ans = mid, l = mid;
        else
            r = mid - 1;
    }
    write(ans), pr(10);
    return 0;
}

这里还有图（从 dx 老师那里搬的）！