题解：P14383 [JOISC 2017] 港口设施 / Port Facility

DFbd · 2026-10-22 10:56:00 · 题解

先转化题目条件，显然当 l_i < l_j < r_i < r_j 时，i,j 不能放到同一边，那么暴力的做法就是暴力建边然后跑二分图染色，但是边数 \mathcal{O}(n^2)。

考虑给每个区间按右端点排序，排完序后就是找 j < i 且 l_j < l_i < r_j 的区间 j 建边。找完之后，直接把当前区间 i 连上找到的所有区间，那么这些区间一定是同色的了，也就是说之后的区间如果要和这些区间连边，只需要连任意一个就可以了。

所以可以把找到的区间合并成一个大区间，每个区间加入一次合并一次，复杂度是 \mathcal{O}(n) 的。

找区间和合并这些区间可以使用线段树，插入区间 [l,r] 就是把 l 的位置赋值成 r，每次就可以用类似于线段树二分的方式找出所有区间并删掉，并求出 minl 和 maxr，把 [minl,maxr] 插入线段树，然后把当前区间插入线段树。

最后跑一遍二分图染色，答案为 2 的连通块数量次方。

#include <bits/stdc++.h>

#define fi first
#define se second
#define int long long

using namespace std;
using pii = pair<int, int>;

const int kMaxN = 2e6 + 5, mod = 1e9 + 7;

int n, L, R, ans = 1, col[kMaxN];
pii a[kMaxN];
vector<int> e[kMaxN];

struct SegTree {
  int t[kMaxN << 3];

  void query(int x, int l, int r, int a) {
    if (l > a || t[x] < a) return;
    if (l == r) {
      L = min(L, l), R = max(R, t[x]);
      e[a].push_back(l), e[l].push_back(a);
      t[x] = -0x3f3f3f3f;
      return;
    }
    int m = l + r >> 1;
    query(x << 1, l, m, a), query(x << 1 | 1, m + 1, r, a);
    t[x] = max(t[x << 1], t[x << 1 | 1]);
  }

  void update(int x, int l, int r, int a, int v) {
    if (l > a || r < a) return;
    if (l == r) {
      t[x] = v;
      return;
    }
    int m = l + r >> 1;
    update(x << 1, l, m, a, v), update(x << 1 | 1, m + 1, r, a, v);
    t[x] = max(t[x << 1], t[x << 1 | 1]);
  }
} tr;

void dfs(int x) {
  for (int i : e[x])
    if (!col[i]) col[i] = 3 - col[x], dfs(i);
    else if (col[i] == col[x]) ans = 0;
}

signed main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
  sort(a + 1, a + n + 1, [](pii a, pii b){ return a.se < b.se; });
  memset(tr.t, -0x3f, sizeof(tr.t));
  for (int i = 1; i <= n; i++) {
    L = 1e9, R = 0, tr.query(1, 1, 2 * n, a[i].fi);
    if (L <= R) tr.update(1, 1, 2 * n, L, R);
    tr.update(1, 1, 2 * n, a[i].fi, a[i].se);
  }
  for (int i = 1; i <= n; i++)
    if (!col[a[i].fi])
      col[a[i].fi] = 1, dfs(a[i].fi), ans = ans * 2 % mod;
  cout << ans;
  return 0;
}