[霍尔定理+线段树]LOJ6062(2017 山东一轮集训 Day2)【Pair】题解

题目概述

两个数 \(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=|\{b_j|a_i+b_j\ge H\}|\) ,然后利用霍尔定理验证。

但是我们不可能指数级枚举子集验证,所以观察下性质可以发现:如果 \(a_i\ge a_j\) ,则 \(M(j)\subseteq M(i)\) 。也就是说对于一个集合,决定这个集合的 \(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;
}

本文链接:https://zigzagk.top/2018/06/01/loj6062
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 CN 许可协议。转载请注明作者和出处QwQ。