自动搬运

查看原文

来自洛谷，原作者为

	caibet AFO (~2025.3.1) | 挑战最搞笑的 OI 生涯

搬运于2025-08-24 22:35:51，当前版本为作者最后更新于2022-01-31 10:24:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更新日志：

• 2022.3.28 发现之前自己通过多写 $6$ 行代码给算法加了个 $\log$，进行了优化。
• 2022.10.17 图挂了，改地址。
• 2023.11.7 发现这个动图不仅和一般图片同样好理解还不容易回顾和思考，因此换成了静态图。同时补充了一些描述。

题意：

给定两个长度为 $n$ 的数列 $a$ 和 $f$。

定义 $\text{Mex}\{l,r\}$ 为 $a$ 数列在区间 $[l,r]$ 里的元素中未出现的最小正整数。

求出最小的 $r-l+1$，使 $f_{r-l+1}<\text{Mex}\{l,r\}$。

解法：

容易看出 $r-l+1$ 代表了区间长度。

既然对于相同的区间长度，$f_{len}$ 的值不变，那么对于每一个长度我们可以找一找最大的 $\text{Mex}$ 值，然后与 $f$ 值进行比较。

显然，这样的贪心思路正确。接下来我们看怎么求同一个长度下最大的 $\text{Mex}$ 值。

题目告诉我们，$\text{Mex}\{l,r\}$ 为 $a$ 数列在区间 $[l,r]$ 里的元素中未出现的最小正整数。

那我们故意找茬，偏偏就让所有正整数依次出现，这样 $\text{Mex}$ 即可达到最大值。

但故意找茬是要吃生瓜蛋子的。如果使 $1,2,3,4,\dots ,k$ 都在区间内的最小区间长度为 $len$，那么长度不小于 $len$ 的区间的最大 $\text{Mex}$ 值才可以扩展为 $k+1$。

我们来用样例解释一下。

那么对于 $a=\{2,3,1,5,4\}$，我们得到了数组 $b=\{2,2,4,4,6\}$，其中 $b_i$ 表示区间长度为 $i$ 时的最大 $\text{Mex}$ 值。

由于 $\text{Mex}$ 值不断增加，所以这样覆盖对于每一个长度得到的 $\text{Mex}$ 值一定是最大的（考虑反证：如果不是最大，则最大的 $\text{Mex}$ 值一定会在之后更新这个长度）。

优化：

从上面可以看出，由于下划线表示的区间是被数字撑大的，所以区间大小不减，最大 $\text{Mex}$ 递增，所以 $b$ 数组单调不减。因而每次扩展区间，我们需要做的，由区间取较大值替换转换为区间覆盖。

同时可以发现，每次区间覆盖的值，也就是当前的 $\text{Mex}$ 值比前一次多一（第一次除外）。于是我们可以使用差分求和。

最后一一比较 $b_i$ 和 $f_i$ 即可。

namespace{
	const int lim=4e6+2;
	int n,a[lim],f[lim],p[lim],b[lim],L=0x7f7f7f7f,R=0;
	void work(){
		n=read();
		F(i,1,<=n) a[i]=read(),p[a[i]]=i;//记录每个数字的位置，方便后续撑大区间时的处理
		F(i,1,<=n) f[i]=read();
		b[1]=1;//第一次实际加上了2，而程序只加了1，因此要提前设置
		F(i,1,<=n){
			L=min(L,p[i]);
			R=max(R,p[i]);//撑大区间
			++b[R-L+1];//差分加
		}
		F(i,1,<=n){
			b[i]+=b[i-1];
			if(f[i]<b[i]){//比较
				cout<<i;
				return;
			}
		}
		cout<<0;
	}
}