题解：AT_joisc2017_b 港湾設備 (Port Facility)

lanos212 · 2024-04-11 09:59:03 · 题解

该题解写得很详细，图比较多，建议不怎么擅长数据结构的阅读。

I. 初步分析得到 O(N^2) 做法

下面将一个物品入栈出栈看作一个区间，具体地，如果一个物品 i 在 A_i 时刻入栈，B_i 时刻出栈，那么这个物品在时间轴上形成一个区间 [A_i,B_i]。

我们先考虑如果只有一个栈，那么其入栈出栈是合法的，当且仅当对于里面的任意两个区间，它们存在包含关系或不相交。

从两面证明条件的充要性：

• 如果存在两区间相交不包含，则会有后入栈的压在先入栈的前面时，先入栈的想要出栈的情况，这是不合法的出入栈情况。

• 如果出现不合法的出入栈情况，也就是考虑当前某物品要出栈时不在栈顶，此时该物品和栈顶物品的区间必然相交且不包含。

那么我们可以暴力 O(N^2) 枚举两个物品的区间，如果它们相交不包含，则在两物品间连一条边。

现在题目要求将每个物品放入 A,B 两个集合中的一个，使得在同一个集合内的物品没有边相连。

这使我们想到二分图。

那么我们暴力建图之后，如果该图不是二分图，则一定无解，答案为 0。

否则答案为二分图合法黑白染色数量，我们考虑二分图的每个联通块都有恰好 2 种染色方式，我们先对该二分图计算其联通块数量 cnt，则答案为 2^{cnt}。

至此，我们获得了一个 O(N^2) 的做法。

II. 减少边数，线段树优化

然而我们发现，这张图建出来，边数可能会是 O(N^2) 级别的：

所以我们如果要优化上述算法，应该从去掉一些不必要的边入手，毕竟我们只需要知道原图是否为二分图，并计算其连通块数量。

考虑前面 O(N^2) 做法，两个物品连边的条件：

• 如果两个物品 i,j 的区间 [A_i,B_i],[A_j,B_j] 满足 A_i<A_j,B_i\in[A_j,B_j]，则 i 与 j 之间连边（如下图）。

那么我们有一种想法：

• 我们在每个区间右端点的地方，存下其物品的编号与区间左端点位置。

• 再枚举每个区间，查找这个区间内的右端点，如果其对应区间的左端点在当前区间的左边，那么连边。

现在这个做法已经有了区间查询的雏形了，我们考虑用线段树进行优化：

• 我们先将所有物品区间按照左端点从小到大排序，然后按这个顺序依次加入线段树。

• 加入时，我们往包含该物品区间右端点的所有线段树上的节点里，加入这个物品区间。（如下图为加入物品区间 [3,6] 的结果）

• 查询时，例如当前物品区间为 [A_i,B_i]，我们就在线段树上查询区间 [A_i,B_i]，然后在每个查询到的线段树节点内，向一个前缀的物品区间连边。（因为你加入是按照左端点从小到大加入的，具体可见下图）

• 优化前缀连边部分，我们对于一个节点内的物品区间，如果其不为当前节点中的第一个，则其连过边就可以直接删除：

这样连边的正确性证明：

• 这样做原本的一条边可能被连多次，不影响图的连通性，以及是否为二分图。

• 关于一条原本应该连，而优化后没连的边（下图中橙色边），都可以被一条长度奇偶性相同的路径（下图中紫色路径）代替，这不改变图的连通性。

• 同时，边被路径替代不会改变图是否为二分图。因为如果图不为二分图，那么存在一个奇环，也就是存在从某一个点开始，走奇数步走回这个点的方案，现在在新图上，走一条原本不存在的边相当于走一条不影响总路径奇偶性的路径，这显然不影响二分图的判定。

对于时间复杂度的分析：

• 一次插入时间复杂度为 O(\log N)，总时间复杂度 O(N \log N)。

• 一次查询经过 O(\log N) 个节点，对节点中第一个物品区间总共连 O(N\log N) 条边。

• 节点中不是第一个物品区间的，在连边后就会被删除，总共连 O(N\log N) 条边。

• 遍历整张图计算答案，时间复杂度 O(N \log N)。

综上所述，该算法时间复杂度为 O(N \log N)。

code（代码使用种类并查集代替遍历，复杂度和上述分析略有不同）

#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int mo = 1e9 + 7;
int n, f[2000001];

inline int find(int x) {
    return (x == f[x] ? x : f[x] = find(f[x]));
}

inline void merge(int x, int y) {
    f[find(x)] = find(y + n);
    f[find(x + n)] = find(y);
}

inline bool cross(pii A, pii B) {
    return ((A.first > B.first && A.first < B.second) ^ (A.second > B.first && A.second < B.second));
}
pii a[1000001];

#define lc (x<<1)
#define rc (x<<1|1)
#define mid ((l+r)>>1)
vector<int> v[8000001];
int ed[8000001];

inline void upd(int x, int l, int r, int id) {
    v[x].push_back(id);

    if (l == r)
        return;

    if (a[id].second <= mid)
        upd(lc, l, mid, id);
    else
        upd(rc, mid + 1, r, id);
}

inline void query(int x, int l, int r, int id) {
    if (l > a[id].second || r < a[id].first)
        return;

    if (l >= a[id].first && r <= a[id].second) {
        if (!ed[x] && !v[x].empty())
            ed[x] = v[x].back();

        if (cross(a[id], a[ed[x]]))
            merge(id, ed[x]);

        while (!v[x].empty() && cross(a[id], a[v[x].back()]))
            merge(id, v[x].back()), v[x].pop_back();

        return;
    }

    query(lc, l, mid, id);
    query(rc, mid + 1, r, id);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;

    for (int i = 1; i <= n + n; ++i)
        f[i] = i;

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

    sort(a + 1, a + n + 1);

    for (int i = n; i; --i)
        upd(1, 1, n + n, i);

    for (int i = 1; i <= n; ++i)
        query(1, 1, n + n, i);

    int cnt = 0;

    for (int i = 1; i <= n; ++i)
        if (find(i) == i)
            ++cnt;

    for (int i = 1; i <= n; ++i)
        if (find(i) == find(i + n)) {
            cout << 0 << '\n';
            return 0;
        }

    int ans = 1;

    while (cnt--)
        ans = ans * 2 % mo;

    cout << ans << '\n';

    return 0;
}