Exhausted[ARC076F]

发表于 分类于 ，

题意

$m$ 张凳子排成一列，从 $1$ 开始编号。

$n$ 个人，第 $i$ 个人能坐在不比 $l_i$ 大的凳子上，或者不比 $r_i$ 小的凳子上。

问最少有多少个人没地方坐。

$n,m\leq 2\times 10^5,l_i<r_i$

题解

还是很显然地假设先建一个二分图出来。那么根据Hall定理，最大匹配 = $|X|-\max{|W|-|N_g(W)|}$。

那么答案就是 $\max { |W|-|N_g(W)|}$。

显然 $N_g(W)$ 只需要考虑所有的 ${ [1,L] \bigcup [R,m]}$ 即可。

若 $L,R$ 固定，则$|W|=\sum{[l_i\leq L]\times [r_i\geq R]}$

把 $L$ 看做 $x$ 轴， $R$ 看做 $y$ 轴，则求 $|W|$ 相当于二维数点问题。

那么答案即为 $\max{|W|-(L+(m-R+1))}=-(L+m+1)+\max{ |W|+R}$

枚举 $L$，将 $(l_i,r_i)$ 按 $l_i$ 排序，扫描线，用线段树维护区间加区间最值即可。

时间复杂度 $O((n+m)\log (n+m))$

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
struct node{
	int l,r;
	friend inline bool operator<(const node &A,const node &B)
	{
		if(A.l!=B.l) return A.l<B.l;
		return A.r<B.r;
	}
}q[N];

int tag[N<<1],mx[N<<1],ls[N<<1],rs[N<<1],cnt;
inline void pushtag(int u,int x){tag[u]+=x; mx[u]+=x;}
inline void pushdown(int u)
{
	if(!tag[u]) return;
	if(ls[u]) pushtag(ls[u],tag[u]);
	if(rs[u]) pushtag(rs[u],tag[u]);
	tag[u]=0;
}
int build(int l,int r)
{
	int u=++cnt;
	if(l==r) {mx[u]=r; return u;}
	int mid=l+r>>1;
	ls[u]=build(l,mid);
	rs[u]=build(mid+1,r);
	mx[u]=max(mx[ls[u]],mx[rs[u]]);
	return u;
}
void add(int u,int l,int r,int L,int R,int x)
{
	if(L<=l&&r<=R) return pushtag(u,x);
	pushdown(u);
	int mid=l+r>>1;
	if(L<=mid) add(ls[u],l,mid,L,R,x);
	if(mid<R)  add(rs[u],mid+1,r,L,R,x);
	mx[u]=max(mx[ls[u]],mx[rs[u]]);
}
int n,m,ans;
int main()
{
	n=read(); m=read();
	fo(i,1,n) q[i].l=read(),q[i].r=read();
	build(0,m+1);
	sort(q+1,q+n+1);
	ans=max(0,n-m);
	for(int i=1,j=0;j<=m;j++)
	{
		for(;i<=n&&q[i].l==j;i++) add(1,0,m+1,0,q[i].r,1);
		ans=max(ans,-(j+m+1)+mx[1]);
	}
	printf("%d",ans);
	return 0;
}