[AtCoder ARC076] F Exhausted?

霍尔定理 + 线段树？

咱学学霍尔定理...

霍尔定理和二分图完美匹配有关，具体而言，就是定义了二分图存在完美匹配的充要条件：

不妨设当前二分图左端集合为 X ，右端集合为 Y ，X 与 Y 之间的边集为 E

令 $\omega(x)$ 表示在 Y 中能通过 E 与 x 中元素相连的元素数量，那么

$\forall x\in X, |x| \le |\omega(x)| $ 为 X 与 Y 存在完美匹配的充要条件...

然后咱发现，多加上 t 个人的话，也就是必然会让 $|\omega(x)|$ 增加 t

那么咱就知道了，t 需要满足以下条件：

\[\forall x\in X, |x| \le |\omega(x)|+t
\]

\[\rightarrow t \ge |x| - |\omega(x)|
\]

\[\rightarrow t \ge |x| +min_R - max_L -1 - m
\]

$min_R$ 和 $max_L$ 表示 x 集合中所有人的最小的 R 和最大的 L

这样咱用线段树搞扫描线就行辣

//by Judge

#include<bits/stdc++.h>

#define Rg register

#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)

#define ll long long

using namespace std;

const int M=2e5+3;

#ifndef Judge

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

#endif

char buf[1<<21],*p1=buf,*p2=buf;

inline int read(){ int x=0,f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;

} int n,m,ans,t[M<<2],Tag[M<<2]; vector<int> val[M];

#define ls k<<1

#define rs k<<1|1

#define mid ((l+r)>>1)

#define lson ls,l,mid

#define rson rs,mid+1,r

inline int Max(int x,int y){ return x>y?x:y; }

inline void pushup(int k){ t[k]=Max(t[ls],t[rs]); }

inline void pushdown(int k){ if(!Tag[k]) return ;

	Tag[ls]+=Tag[k],Tag[rs]+=Tag[k];

	t[ls]+=Tag[k],t[rs]+=Tag[k],Tag[k]=0;

}

void build(int k,int l,int r){

	if(l==r) return t[k]=l,void();

	build(lson),build(rson),pushup(k);

}

void update(int k,int l,int r,int L,int R){

	if(L<=l&&r<=R) return ++Tag[k],++t[k],void(); if(l>R||L>r) return ;

	pushdown(k),update(lson,L,R),update(rson,L,R),pushup(k);

}

int query(int k,int l,int r,int L,int R){

	if(L<=l&&r<=R) return t[k]; if(l>R||L>r) return 0;

	return pushdown(k),Max(query(lson,L,R),query(rson,L,R));

}

int main(){ int l,r; n=read(),m=read()+1,ans=n-m+1;

	fp(i,1,n) l=read(),r=read(),val[l].push_back(r);

	build(1,0,m);

	fp(L,0,m-1){

		fp(j,0,val[L].size()-1) update(1,0,m,0,val[L][j]);

		ans=Max(ans,query(1,0,m,L+1,m)-m-L);

	} return !printf("%d\n",ans);

}

巴特西

[AtCoder ARC076] F Exhausted?

最新文章

热门文章