题目概述

两个数 $x,y​$ 可以匹配定义为 $x+y\ge H​$ 。现在给出 $\{a_n\}​$ 和 $\{b_m\}​$ ，问 $\{a_n\}​$ 有多少个连续子序列满足：存在一种方法使得连续子序列与 $\{b_m\}​$ 两两匹配。

解题报告

我怎么霍尔定理都不会啊，考前临时抱佛脚。

霍尔定理：若二分图 $X,Y$ 存在完美匹配，则对于 $X$ 的任意子集 $S$ ，定义 $M(S)$ 表示 $S$ 连向的点的集合，均满足 $|S|\le |M(S)|$ 。yy一下还是挺显然的，反正我不会证明。

知道霍尔定理就可做了。题目显然就是要我们验证 $\{a_n\}$ 的 $n-m$ 个连续子序列是否与 $\{b_m\}$ 有完美匹配。我们可以先求出 $num_i=|\{a_i+b_j\ge H\}|$ ，然后利用霍尔定理验证。

但是我们不可能指数级枚举子集验证，所以观察下性质可以发现：如果 $a_i\ge a_j$ ，则 $M(i)>M(j)$ 。也就是说对于一个集合，决定这个集合的 $M$ 集合的点是 $a_{max}$ 。

这就很Easy了，对于一个排序之后的连续子序列 $\{c_m\}$ ，我们要验证 $\forall num_i\ge i$ ，也就是说 $min\{num_i-i\}\ge 0$ ，用线段树维护最小值即可。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=150000;

int n,m,H,a[maxn+5],b[maxn+5],ID[maxn+5],rk[maxn+5],ans;
int num[maxn+5],INF,MIN[(maxn<<2)+5],tag[(maxn<<2)+5];

inline bool cmp (const int &A,const int &B) {return a[A]<a[B];}
#define Addtag(k,p) (MIN[p]+=(k),tag[p]+=(k))
#define Pushdown(p) (tag[p]?(Addtag(tag[p],(p)<<1),Addtag(tag[p],(p)<<1|1),tag[p]=0):0)
inline void Insert(int L,int R,int k,int l=1,int r=n,int p=1){
    if (R<l||r<L) return;if (L<=l&&r<=R) {Addtag(k,p);return;}Pushdown(p);int mid=l+(r-l>>1);
    Insert(L,R,k,l,mid,p<<1);Insert(L,R,k,mid+1,r,p<<1|1);MIN[p]=min(MIN[p<<1],MIN[p<<1|1]);
}
inline int Find(int x,int L=1,int R=m) {
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        b[mid]>=x?R=mid-1:L=mid+1;return L;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&m,&H);memset(MIN,63,sizeof(MIN));INF=MIN[0];
    for (int i=1;i<=m;i++) scanf("%d",&b[i]);
    for (int i=1;i<=n;i++) scanf("%d",&a[ID[i]=i]);
    sort(ID+1,ID+1+n,cmp);sort(b+1,b+1+m);
    for (int i=1;i<=n;i++) rk[ID[i]]=i,num[i]=m-Find(H-a[i])+1;
    for (int i=1;i<=m;i++) Insert(rk[i],rk[i],num[i]-1-INF),Insert(rk[i]+1,n,-1);ans+=MIN[1]>=0;
    for (int i=m+1;i<=n;i++){
        Insert(rk[i-m],rk[i-m],INF-num[i-m]+1);Insert(rk[i-m]+1,n,1);
        Insert(rk[i],rk[i],num[i]-1-INF);Insert(rk[i]+1,n,-1);ans+=MIN[1]>=0;
    }
    return printf("%d\n",ans),0;
}