定理内容

对于二分图中的集合 $X$和 $Y$（$|X| \leq |Y|$），任取一个 $X$的子集 $s$（$s \subseteq X$），设 $Y$中与 $s$有边相连的点集为 $N(s)$，若 $X$和 $Y$存在完美匹配（完美匹配指的是匹配数 $= |X|$），则一定满足 $|s| \leq |N(s)|$

反之亦然，即这是该图存在完美匹配的充要条件

（中文音译叫霍尔定理）

正确性证明

必要性

若某个奇妙♂の图存在完美匹配，且不满足 Hall 定理

那么就有 $k$个点，连出去的点不足 $k$个

那谁跟它们匹配吖？

_(:зゝ∠)_

充分性

若某个奇妙♂の图不存在完美匹配，且满足 Hall 定理

那么它的最大匹配状态下，至少有一个点 $a$未匹配

根据 Hall 定理，有至少一个和它相连的对面的点 $b$

若这个点 $b$不在最大匹配中，那。。。$ab$就能匹配了呀

所以点 $b$在最大匹配中，那么一定有一个点 $c$与点 $b$匹配

根据霍尔定律，$Y$中与 $a$和 $c$相连的点的数目 $\geq 2$，因此除了点 $b$外，一定至少还有一个点与点 $c$相邻。。。

这样下去就一定能找到一条增广路，与一开始我们假设的条件矛盾，因此得证

例题

「2017 山东一轮集训 Day2」Pair LOJ – 6062

由于 $a, b$是独立的，因此可以看成二分图

由于 $b$的顺序与答案无关，因此可以先把 $b$从小打到排个序

设当前枚举的连续的一段 $a$的子数列为集合 $X$

对于 $b _ i$来说，$X$中与 $b _ 1, b _ 2, b _ 3, …, b _ { i – 1 }$相邻的点都一定与 $b _ i$相邻

因此在 $b$中选择一个子集 $k$，若 $b _ i$是 $k$中最大元素，那么 $|N(k)|$就等于 $X$中与 $b _ i$相邻的点数，且 $|k|$的最大取值就是 $i$，需要满足 $|N(k)| \geq |k|$

也就是说要求 $X$中与 $b _ i$相邻的点数要 $\geq i$

所以我们要维护 $X$中与 $b _ i$相邻的点数

注意到对于每个 $a _ i$，与其相邻的点集是 $b$的一个连续后缀，因此可以用线段树维护

代码：

#include <bits/stdc++.h>

#define NS (150005)
#define LS(a) ((a) << 1)
#define RS(a) ((a) << 1 | 1)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, h, A[NS], B[NS], ans;

struct N {int mn, tag;} e[NS << 2];

void pup(int a) { e[a].mn = min(e[LS(a)].mn, e[RS(a)].mn); }

void pdown(int a)
{
    if (!e[a].tag) return;
    int l = LS(a), r = RS(a);
    e[l].mn += e[a].tag, e[l].tag += e[a].tag;
    e[r].mn += e[a].tag, e[r].tag += e[a].tag;
    e[a].tag = 0;
}

void build(int l, int r, int a)
{
    if (l == r) { e[a].mn = -l; return; }
    int mid = (l + r) >> 1;
    build(l, mid, LS(a)), build(mid + 1, r, RS(a)), pup(a);
}

void add(int l, int r, int d, int L, int R, int a)
{
    if (l <= L && R <= r) { e[a].mn += d, e[a].tag += d; return; }
    pdown(a);
    int Mid = (L + R) >> 1;
    if (l <= Mid) add(l, r, d, L, Mid, LS(a));
    if (r > Mid) add(l, r, d, Mid + 1, R, RS(a));
    pup(a);
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), IN(h);
    for (int i = 1; i <= m; i += 1) IN(B[i]);
    for (int i = 1; i <= n; i += 1) IN(A[i]);
    sort(B + 1, B + 1 + m), build(1, m, 1);
    for (int i = 1; i < m; i += 1)
    {
        int j = lower_bound(B + 1, B + 1 + m, h - A[i]) - B;
        if (j <= m) add(j, m, 1, 1, m, 1);
    }
    for (int i = m; i <= n; i += 1)
    {
        int j = lower_bound(B + 1, B + 1 + m, h - A[i]) - B;
        if (j <= m) add(j, m, 1, 1, m, 1);
        if (e[1].mn >= 0) ans++;
        j = lower_bound(B + 1, B + 1 + m, h - A[i - m + 1]) - B;
        if (j <= m) add(j, m, -1, 1, m, 1);
    }
    printf("%d\n", ans);
    return 0;
}