给定序列 $c, w$

对于 $w_i \gt c_j$，则 $w_i$ 可以匹配 $c_j$。

在满足最大匹配的基础上，顺次输出匹配每个 $c_j$ 的 $w_i$，要求输出的字典序最大。

题解：

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

问题

1. 题解结论的证明。因为如果不是最小值，说明还存在 $w_i$ 没有匹配；如果是最小值，则之后的都有匹配。这样证明是否正确？
2. 关于题解的实现。为什么可以用线段树求最大匹配，以及二分来求最大匹配以及最大字典序的正确性如何证明？

std

#include<bits/stdc++.h>
using namespace std;
const int N=37000005,mod=1e9+7;
int turn,n,a[N],f[N],t[N];
void Sol(){
	for(int i=0;i<=n;++i)
		t[i]=0;
	for(int i=1;i<=n;++i)
		++t[a[i]];
	int mex=0;
	while(t[mex])++mex;

	for(int i=0;i<=n;++i)
		t[i]=0;
	f[0]=1;
	for(int i=1,j=1,k=0;i<=n;++i){
		++t[a[i]];
		while(t[k])++k;
		if(k==mex){
			while(j<i&&(a[j]>mex||t[a[j]]>1))--t[a[j++]];
			f[i]=f[i-1]+f[j-1];
			if(f[i]>=mod)
				f[i]-=mod;
		}
		else
			f[i]=f[i-1];
	}
	printf("%d\n",(f[n]-f[n-1]+mod)%mod);
}

int main(){
	freopen("clods.in","r",stdin);
	freopen("clods.out","w",stdout);
	scanf("%d",&turn);
	while(turn--){
		scanf("%d",&n);
		if(n<N-5){
			for(int i=1;i<=n;++i)
				scanf("%d",&a[i]);
		}
		else{
			int x,y;
			scanf("%d%d",&x,&y);
			for(int i=2;i<=n;++i)
				a[i]=(a[i-1]*x+y+i)&262143;
		}
		Sol();
	}
	return 0;
}