资讯详情

Hall 定理

Hall 定理是一个判定二分图是否存在完美匹配的定理。在这里，一个二分图 \(G(U_1, U_2, E)\)（左部点，右部点，边集）存在完美匹配，当且仅当有一种匹配，满足 \(U_1\) 中所有点均被匹配。

Hall 定理：一个二分图 \(G(U_1, U_2, E)\) 存在完美匹配，当且仅当 \(\forall S \subseteq U_1, |N(S)| \ge |S|\)，这里 \(N(S)\) 代表 \(U_2\) 中所有与 \(S\) 中的点直接相连的点集（我们将这个条件记为 \(C\)）。

我们采用归纳法证明，\(U_1 = 1\) 的情况，Hall 显然成立。

现在我们有：

• \(|U_1| = X\)。\((1)\)

• \(G(U_1, U_2, E)\) 满足 \(C\)。\((2)\)

• 对于所有 \(|U_1|' < X\) 的 \(G'\)，Hall 定理成立。\((3)\)

我们想证明：\(G\) 有完美匹配。

我们的思路是将 \(U_1\) 拆分为更小的集合，考虑两种情形：

1. \(\exists T \subset U_1, |T| = |N(T)|\)。由于 \((3)\)，\(T\) 满足 Hall 定理，又 \((2)\)，\(T\) 作为 \(U_1\) 的一个子集肯定也满足 \(C\)，所以 \(T\) 存在完美匹配。我们先把 \(T\) 内的完美匹配连上，考虑将 \(U_1 \backslash T\) 匹配 \(U_2 \backslash N(T)\)。考虑 \(G'(U_1 \backslash T, U_2 \backslash N(T), E)\)，如果 \(\exists W \subseteq U_1 \backslash T, |N(W) < W|\)，那么 \(|N(W) \cup N(T)| < |W| + |T|\)，但是由于 \((2)\)，所以这种情况不存在。因此 \(G'\) 满足条件 \(C\)，存在完美匹配。所以 \(G\) 满足 Hall 定理。

2. \(\forall T \subset U_1, |T| > |N(T)|\)。这种情况就更好证明了😄，我们直接随便选一个 \(x \in U_1\)，让它随便配一个 \(y \in U_2\)。然后考虑 \(G'(U_1 \backslash x, U_2 \backslash y, E)\) 是否满足条件 C。这个是显然的，因为 \(U_2\) 去除了 \(y\) 后，\(\forall T \subset (U_1 \backslash x)\)，\(N(T)\) 大小最多减少 \(1\)，但是我们一开始有 \(|N(T)| > |T|\)，所以现在 \(|N(T)| \ge |T|\)，所以 \(G'\) 依然满足 \(C\)。\(G\) 满足 Hall 定理。

这两种情形可以覆盖所有情况。归纳完毕。

P10208 [JOI 2024 Final] 礼物交换

问题：给定数组 \(A\)，\(B\)，每次询问区间 \([l,r]\) 内是否存在一个 \([l, l + 1, ..., r]\) 的重排 \(P\)，满足 \(P_i \neq i, A_{P_i} \ge B_i\)。数据范围 \(N, Q \le 5 \cdot 10^5\)。

这里着重探讨一下合法的结论。

考虑不一定满足 \(P_i \neq i\) 的弱化版：对于学生集合 \(U_1\)，\(N(U_1) = \{ j | A_j \ge \min(B_i), i \in U_1 \}\)。因此，我们只需要将 \(A[l...r]\)，\(B[l...r]\) 从小到大排序后，考虑 \(B[l...r]\) 的每一个后缀即可。

根据 Hall 定理，\([l, l + 1, l + 2, ..., r]\) 存在二分图完美匹配，当且仅当排序后 \(\forall i, A_i \ge B_i\)。这也是符合贪心直觉的。

加入 \(P_i \neq i\)，我们依旧考虑运用 Hall。对于每一个数 \(B_i\)，必须要满足 \(\#\{A_i \ge B_i \} \ge 2\)。这样 \(N(\{B_i\}) \ge 1\)。但是光这样还不够，这个集合里所有的元素都必须要被更大的用呢？因此我们还要有 \(cntA(\ge B_j) \ge \#\{B_i > A_j\} + 2\)。

这三个性质首先缺一不可，其次是完备的，Deepseek 给出了一个很好的解释：

对于三个性质，分别拿一个数据结构维护即可。

#include <bits/stdc++.h>
#define int long long
#define Misaka namespace
#define Network std
using Misaka Network;// P10208 [JOI 2024 Final] 礼物交换
// 结论(Hall 定理): 区间 [l,r] 可行 ⟺ 任意线段 [B_i, A_i] 与其它线段有交
// 预处理 L[i]/R[i] = 左右最近的相交线段, 坏点 (l,r) 满足 L[i]<l<=i<=r<R[i]
// 每个 i 贡献矩形 (l∈[L[i]+1,i], r∈[i,R[i]-1]), 离线扫描线 + BIT 差分const int N = 5e5 + 7, M = 1e6 + 7;
int n, q, A[N], B[N], L[N], R[N];
int mx[M << 2], tag[M << 2];void push(int p){if(tag[p]){tag[p << 1] = tag[p << 1 | 1] = tag[p];mx[p << 1] = mx[p << 1 | 1] = tag[p];tag[p] = 0;}
}
void upd_max(int p, int l, int r, int ql, int qr, int v){if(ql <= l && r <= qr){ mx[p] = tag[p] = v; return; }push(p);int mid = (l + r) >> 1;if(ql <= mid) upd_max(p << 1, l, mid, ql, qr, v);if(qr > mid) upd_max(p << 1 | 1, mid + 1, r, ql, qr, v);mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
}
int qry_max(int p, int l, int r, int ql, int qr){if(ql <= l && r <= qr) return mx[p];push(p);int mid = (l + r) >> 1, res = 0;if(ql <= mid) res = max(res, qry_max(p << 1, l, mid, ql, qr));if(qr > mid) res = max(res, qry_max(p << 1 | 1, mid + 1, r, ql, qr));return res;
}
void upd_min(int p, int l, int r, int ql, int qr, int v){if(ql <= l && r <= qr){ mx[p] = tag[p] = v; return; }push(p);int mid = (l + r) >> 1;if(ql <= mid) upd_min(p << 1, l, mid, ql, qr, v);if(qr > mid) upd_min(p << 1 | 1, mid + 1, r, ql, qr, v);mx[p] = min(mx[p << 1], mx[p << 1 | 1]);
}
int qry_min(int p, int l, int r, int ql, int qr){if(ql <= l && r <= qr) return mx[p];push(p);int mid = (l + r) >> 1, res = n + 1;if(ql <= mid) res = min(res, qry_min(p << 1, l, mid, ql, qr));if(qr > mid) res = min(res, qry_min(p << 1 | 1, mid + 1, r, ql, qr));return res;
}int tr[N];
void add(int p, int v){ for(; p <= n + 1; p += p & -p) tr[p] += v; }
int sum(int p){ int s = 0; for(; p; p -= p & -p) s += tr[p]; return s; }vector<pair<int, int> > addE[N + 1], remE[N + 1], qs[N + 1];
bool ans[N];signed main(){ios::sync_with_stdio(0), cin.tie(0);cin >> n;for(int i = 1; i <= n; i++) cin >> A[i];for(int i = 1; i <= n; i++) cin >> B[i];cin >> q;for(int i = 1; i <= n; i++){L[i] = qry_max(1, 1, 2 * n, B[i], A[i]);upd_max(1, 1, 2 * n, B[i], A[i], i);}fill(mx, mx + (M << 2), n + 1);fill(tag, tag + (M << 2), 0);for(int i = n; i >= 1; i--){R[i] = qry_min(1, 1, 2 * n, B[i], A[i]);upd_min(1, 1, 2 * n, B[i], A[i], i);}for(int i = 1; i <= n; i++){addE[i].push_back({L[i] + 1, i});if(R[i] <= n) remE[R[i]].push_back({L[i] + 1, i});}for(int i = 1; i <= q; i++){int l, r; cin >> l >> r;qs[r].push_back({l, i});}for(int r = 1; r <= n; r++){for(auto [a, b] : addE[r]){ add(a, 1); add(b + 1, -1); }for(auto [a, b] : remE[r]){ add(a, -1); add(b + 1, 1); }for(auto [l, id] : qs[r]) ans[id] = (sum(l) == 0);}for(int i = 1; i <= q; i++) cout << (ans[i] ? "Yes" : "No") << "\n";return 0;
}