Codeforces 1278D 题解

给你 \(n\) ( \(1\leqslant n\leqslant 5\cdot 10^5\) ) 条线段 \([l_1, r_1], [l_2, r_2], \cdots, [l_n, r_n]\) ( \(1\le l_i < r_i\le 2n\) )。保证每条线段的端点为整数，且 \(\forall i, j\) ( \(i \ne j\) )，不存在 \(l_i = l_j\) 或 \(r_i = r_j\)，不存在 \(r_i = l_j\)。

现在用这 \(n\) 个点构建一个图，结点 \(u, v\) 有边相连当且仅当 \([l_u, r_u]\) 和 \([l_v, r_v]\) 相交，但其中任意一个均不包含另一个。

你的任务是判断这个图是否是一棵树。

考虑一个图成为一棵树的充分必要条件：所有点互相联通，并且一共有 \(n - 1\) 条边。

考虑 \(i, j\) 能连边的条件：

1. \(l_i < l_j\)
2. \(l_j < r_i < r_j\)。

于是将线段按左端点排序之后可以用二维偏序求出边的数量。

接着考虑使用并查集维护联通块，用 set <pair <int, int> > 插入 make_pair(r_i, i) 后将所有满足 \(l_j < r_i < r_j\) 的 \(i, j\) 连边即可。

这里有个细节，一定要在求完边数量并确保它等于 \(n - 1\) 后再连边，否则连边的数量可能会到 \(\mathcal{O}(n^2)\)。

code:

#include <bits/stdc++.h>
#include <cmath>
using namespace std;
int n;
vector <int> c, fa;
vector <pair <int, int> > tg;
set <pair <int, int> > s;
void insert(int x, int v) {for (; x <= 2 * n; x += x & -x) c[x] += v;}
int query(int x) {int r = 0; for (; x; x -= x & -x) r += c[x]; return r;}
signed main(void) {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    c.assign(2 * n + 1, 0);
    tg.assign(2 * n + 1, {});
    fa.assign(n, 0);
    for (int i(0); i < n; ++i) fa[i] = i;
    function <int(int)> find = [&](int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    } ;
    for (int i(0); i < n; ++i) {
        int l, r; cin >> l >> r;
        tg[l] = make_pair(r, i);
        tg[r] = make_pair(-l, i);
    }
    unsigned long long ans = 0;
    for (int i(1); i <= 2 * n; ++i) {
        int kl, kr; tie(kl, kr) = tg[i];
        if (kl < 0) insert(-kl, -1);
        else ans += query(kl) - query(i), insert(kl, 1);
    }
    if (ans != n - 1) return (cout << "NO\n"), 0;
    for (int i(1); i <= 2 * n; ++i) {
        int kl = tg[i].first, kr = tg[i].second;
        if (kl < 0) s.erase(s.find(make_pair(i, kr)));
        else {
            auto k = s.lower_bound(make_pair(i, 0));
            for (auto k = s.lower_bound(make_pair(i, 0)); k != s.end() && k -> first < kl; k = next(k)) {
                int father = find(k -> second);
                fa[father] = find(kr);
            }
            s.insert(make_pair(kl ,kr));
        }
    }
    bool flg = 0;
    for (int i(1); i < n; ++i) if (find(i) != find(0)) flg = 1;
    cout << (!flg ? "YES\n" : "NO\n");
    return 0;
}