@description@
给出一个长度为 n 的数列 {ai} 与一个长度为 m 的数列 {bi}，求 {ai} 有多少个长度为 m 的连续子数列与 {bi} 匹配。
两个数列可以匹配，当且仅当存在一种方案，使两个数列中的数可以两两配对。
两个数可以配对，当且仅当它们的和不小于 h。
输入格式
第一行三个整数 n, m, h。
第二行有 m 个数字 b1, b2, ..., bm。
第三行有 n 个数字 a1, a2, ..., an。
输出格式
输出一个数字，{ai} 有多少个长度为 m 的连续子数列能与 {bi} 匹配。
样例
样例输入 1
5 2 10
5 3
1 8 5 5 7
样例输出 1
2
数据范围与提示
对于 100% 的数据，1 <= m <= n <= 150000；1 <= ai, bi, h <= 10^9。
@solution@
这里的匹配其实就是二分图的匹配。
然而这个数据范围，如果真的写二分图匹配，怕是连边都建不出来。
但这道题只需要询问二分图最大匹配的存在性，而我们有 hall 定理描述了二分图最大匹配存在性。
hall 定理表明，从二分图左边任选一个点集 S，取出与 S 中的点有边相连的右边的点，构成邻集 T。若对于任意一个 S 都满足 |S| <= |T|，则二分图最大匹配存在。
我们一般用的时候，需要尝试去找一个不满足 hall 定理的点集，即 |S| > |T| 的点集 S，或者等价地记作 |S| - |T| > 0。
注意这道题有个性质：如果 ai >= aj，则 aj 所连的 bk，ai 也能够连向 bk。这个比较显然，因为 ai + bk >= aj + bk >= h。
于是我们设点集 S 中权值最大的为 ax，显然 S 对应的 T 是由 ax 的值唯一决定的。于是如果要让 |S| - |T| > 0，就是尽可能地要让 S 大，可以发现最大是把所有 <= ax 的全部塞进 S 里面。
先处理出使 ai + bj >= h 的 bj 数量，记作 f[i]。
对于一个二分图，我们有 O(n) 的检验方法：对于每一个 i，统计这个二分图内 aj <= ai 的 j 的个数 p，判断是否 p - f[i] > 0，如果是则无法匹配。
注意到每次二分图的变化只会多一个点 + 少一个点，所以我们可以对权值建线段树，快速维护出 p - f[i] 的最大值（代码中所呈现的是 f[i] - p 的最小值）。
@accepted code@
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 150000;
int d[MAXN + 5], dcnt = 0;
int a[MAXN + 5], b[MAXN + 5];
int n, m, h;
struct segtree{
#define lch x<<1
#define rch x<<1|1
struct node{
int l, r;
int tg, mn;
}t[4*MAXN + 5];
void pushup(int x) {t[x].mn = min(t[lch].mn, t[rch].mn);}
void pushdown(int x) {
if( t[x].tg ) {
t[lch].tg += t[x].tg, t[lch].mn += t[x].tg;
t[rch].tg += t[x].tg, t[rch].mn += t[x].tg;
t[x].tg = 0;
}
}
void build(int x, int l, int r) {
t[x].l = l, t[x].r = r, t[x].tg = t[x].mn = 0;
if( l == r ) return ;
int mid = (l + r) >> 1;
build(lch, l, mid), build(rch, mid + 1, r);
}
void modify(int x, int l, int r, int d) {
if( l > t[x].r || r < t[x].l )
return ;
if( l <= t[x].l && t[x].r <= r ) {
t[x].mn += d, t[x].tg += d;
return ;
}
pushdown(x);
modify(x << 1, l, r, d);
modify(x << 1 | 1, l, r, d);
pushup(x);
}
}T;
int main() {
scanf("%d%d%d", &n, &m, &h);
for(int i=1;i<=m;i++)
scanf("%d", &b[i]);
for(int i=1;i<=n;i++)
scanf("%d", &a[i]), d[++dcnt] = a[i];
sort(d + 1, d + dcnt + 1);
dcnt = unique(d + 1, d + dcnt + 1) - d - 1;
T.build(1, 1, dcnt);
for(int i=1;i<=m;i++)
T.modify(1, lower_bound(d + 1, d + dcnt + 1, h - b[i]) - d, dcnt, 1);
for(int i=1;i<=n;i++)
a[i] = lower_bound(d + 1, d + dcnt + 1, a[i]) - d;
for(int i=1;i<=m;i++) T.modify(1, a[i], dcnt, -1);
int ans = (T.t[1].mn >= 0);
for(int i=m+1;i<=n;i++) {
T.modify(1, a[i], dcnt, -1), T.modify(1, a[i-m], dcnt, 1);
ans += (T.t[1].mn >= 0);
}
printf("%d
", ans);
}
@details@
代码中处理 f[i] 的时候是直接在线段树中加加减减。
其他的。。。应该就没有什么值得注意的细节了吧。