给定序列 $a, b$。

对于任意 $b_j \gt a_i$，则 $b_j$ 可以匹配 $a_i$。

然后输出匹配每个 $a_i$ 的 $b_j$，要求字典序最大。

题解： 考虑 Hall 定理， 将 $a_i$ 和 $b_i$ 一起排序，得到序列，将 $a_i$ 视为 $1$，$b_i$ 视为 $-1$，那么答案就是 $n +$ 前缀和的最小值。

问题

1. 证明题解的结论。因为如果不是最小值，说明还存在 $b_i$ 没有匹配；如果是最小值，则之后的都有匹配。这个思路是否正确？

2. 关于题解的实现。不理解为什么这样能求最大匹配，以及为什么要二分。

std

#include<bits/stdc++.h>
using namespace std;
int n;
int c[500005],w[500005];
int cl[500005],pre[500005];
int ans[500005];
struct neg{
	int t[500005<<2];
	void pushup(int rt)
	{
		t[rt]=min(t[rt<<1],t[rt<<1|1]);
	}
	void build(int rt,int l,int r)
	{
		if(l==r) {t[rt]=c[l];return ;}
		int mid=(l+r)>>1;
		build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
		pushup(rt);
	}
	void update(int rt,int l,int r,int pos,int w)
	{
		if(l==r) {t[rt]=w;return;}
		int mid=(l+r)>>1;
		if(pos<=mid) update(rt<<1,l,mid,pos,w);
		else update(rt<<1|1,mid+1,r,pos,w);
		pushup(rt);
	}
	int queryl(int rt,int l,int r,int w){
		if(l==r) return t[rt]<w?l:1e9;
		int mid=(l+r)>>1;
		if(t[rt<<1]<w) return queryl(rt<<1,l,mid,w);
		return queryl(rt<<1|1,mid+1,r,w);
	}
	int queryr(int rt,int l,int r,int w)
	{
		if(l==r) return t[rt]<w?l:1e9;
		int mid=(l+r)>>1;
		if(t[rt<<1|1]<w) return queryr(rt<<1|1,mid+1,r,w);
		return queryr(rt<<1,l,mid,w);
	}
}T1,T2;
int main()
{
	freopen("uphill.in","r",stdin);
	freopen("uphill.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int i=1;i<=n;i++) cin>>w[i];
	sort(w+1,w+1+n);
	T1.build(1,1,n);T2.build(1,1,n);
	for(int i=1;i<=n;++i)
	{
		int zc=T1.queryr(1,1,n,w[i]);
		if(zc!=1e9)
		{
			cl[i]=zc;pre[zc]=i;
			T1.update(1,1,n,zc,2e9);
		}
	}
	for(int i=n;i>=1;i--)
	{
		int zc=0;
		if(!cl[i])
		{
			zc=T2.queryl(1,1,n,2e9);
			cl[pre[zc]]=0;
		}
		else{
			T1.update(1,1,n,cl[i],c[cl[i]]);
			zc=T1.queryl(1,1,n,w[i]);
		}
		ans[zc]=w[i];
		T1.update(1,1,n,zc,2e9);
		T2.update(1,1,n,zc,2e9);
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
}