Hall 定理

这是一个关于二分图完美匹配存在性的定理。定理内容如下：将二分图分为左部点 $L$ 和右部点 $R$，保证 $|L| = |R|$，该图存在完美匹配当且仅当对于 $\forall S \subseteq L, |f(S)| \ge |S|$，其中 $f(S)$ 表示 $R$ 中与 $S$ 中点有连边的点的集合。这个可以归纳法证明，感性理解可以参考这篇文章，个人认为写得很生动形象。

我们来看一些例题。

P3488

我将这个题当作 Hall 定理应用的模板题，我会着重解释为什么可以将这个 Hall 定理的形式转化为一个最大子段和。

如果不考虑数据范围，那就是一个二分图最大匹配裸题。但是这数据范围太大，我们不能暴力建边，考虑霍尔定理。我们将脚的大小当作一种类型（左部点），$num_i$ 指脚大小为 $i$ 的人的个数，右部点是鞋的尺码，也可以将每种尺码的 $k$ 双鞋都看作在此位置上的 $k$ 个右部点。取 $S \subseteq L$，那么只有对于 $\forall S$ 都满足 $\sum\limits_{i \in S} num_i \le |f(S)|$ 才会有完美匹配。现在我们就要使得这个上界最紧。考虑这样一件事，如果我们选择的 $S$ 并不是一段连续区间，那么假如 $S \cup T = [l, r], S \cap T = \varnothing$，且 $S, T$ 分别满足上界的限制，那么设 $A = S \cup T$，则$|A| = |S| + |T|$，但是 $|f(A)| \le |f(S)| + |f(T)|$，因为 $f(S)$ 和 $f(T)$ 可能有相同元素。所以我们可以发现，如果取 $S$ 为一段连续的区间 $[l, r]$，得到的上界一定不松于不连续的 $S$。

于是现在我们讨论 $S = [l, r]$，那么就是 $f(S) = k \times (r + d - l + 1)$，上界就是，

$$\begin{aligned} \sum\limits_{i = l}^{r} num_i &\le k \times (r + d - l + 1) \\ &= k \times d + k \times (r - l + 1) \end{aligned}$$

即：

$$\sum\limits_{i = l}^{r} (num_i - k) \le k \times d$$

很好，你会发现 $k \times d$ 是一个定值，所以我们只需要求出最大的 $\sum\limits_{i = l}^{r} (num_i - k)$ 且满足 $1 \le l \le r \le n$，如果这个最大的和 $\le n$，那么所有的 $S$ 都会满足上界条件了，所以就一定存在完美匹配，反之不存在。这是一个简单的线段树维护最大子段和问题，具体可以参考 P4513。

给出丑陋的代码。

#include <bits/stdc++.h>
#define ll long long
#define lc p << 1
#define rc p << 1 | 1
using namespace std;
const int N = 2e5 + 5;
int n, m, k, d;

namespace SegT{
    struct Rinne{
        ll lx, rx, ans, sum;
        friend Rinne operator+(const Rinne a, const Rinne b) {
            Rinne c;
            c.sum = a.sum + b.sum;
            c.lx = max(a.lx, a.sum + b.lx);
            c.rx = max(b.rx, b.sum + a.rx);
            c.ans = max(a.rx + b.lx, max(a.ans, b.ans));
            return c;
        }
    } tr[N << 2];
    void pushup(int p) {
        tr[p] = tr[lc] + tr[rc]; return ;
    }
    void build(int p, int l, int r) {
        if(l == r) {
            tr[p].sum = -k, tr[p].ans = tr[p].lx = tr[p].rx = 0;
            return ;
        }
        int mid = (l + r) >> 1;
        build(lc, l, mid), build(rc, mid + 1, r);
        pushup(p); return ;
    }
    void modify(int p, int l, int r, int x, int v) {
        if(l == r && l == x) {
            tr[p].sum += v;
            tr[p].ans = tr[p].lx = tr[p].rx = max(tr[p].sum, 0ll);
            return ;
        }
        int mid = (l + r) >> 1;
        if(x <= mid) modify(lc, l, mid, x, v);
        else modify(rc, mid + 1, r, x, v);
        pushup(p); return ;
    }
    void modify(int x, int v) {
        modify(1, 1, n, x, v);
    }
} using namespace SegT;

int main() {
    scanf("%d %d %d %d", &n, &m, &k, &d);
    ll lim = 1ll * k * d;
    build(1, 1, n);
    for (int i = 1; i <= m; ++i) {
        int x, v; scanf("%d %d", &x, &v);
        modify(x, v);
        if(tr[1].ans <= lim) puts("TAK");
        else puts("NIE");
    }
    return 0;
}