自动搬运

查看原文

来自洛谷，原作者为

	retep 离谱！世界太离谱了！（关注必互关）

搬运于2025-08-24 22:39:07，当前版本为作者最后更新于2022-07-25 00:05:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目简述

给定序列 $\{a_n\},\{b_n\}$，求一个序列 $\{c_n\}$ 满足 $\forall i\in[1,n],c_i\in\{a_i,b_i\}$，最大化

$$\max\{r-l+1-\operatorname{mex}\{c_l,c_{l+1},\dots, c_{r-1},c_r\}\}(1\le l\le r\le n) $$

并输出该式子可能的最大值。

其中 $\operatorname{mex}\{c_l,c_{l+1},\dots,c_{r-1},c_r\}$ 指的是 $c_l,c_{l+1},\dots,c_{r-1},c_r$ 中没有出现过的最小非负整数。

数据范围：$1\le n \le 10^6$，$0\le a_i,b_i \le n$

题目传送门：P8445 射命丸文的取材之旅

题目分析

这是道最优化问题，关键点在于枚举对象的选择。

枚举 $l$ 与 $r$ 显然是不可行的，因为枚举子区间本身就是 $O(n^2)$，再加上区间内还要抉择选 $a_i$ 还是 $b_i$ 让复杂度进一步上升。

看到数据范围，我们发现了异常：$0\le a_i,b_i \le n$，为什么是 $n$ 呢，为什么不是 $1e9$ 或 $1e18$ 呢？这其中一定有蹊跷，并且一定是解题的关键。

通常的思路为枚举区间，然后计算其中 $\operatorname{mex}$ 的最小值，但我们已经知道这个方法是行不通的，于是反其道而行之，考虑是否可以枚举 $\operatorname{mex}$ 的值，然后计算区间的最大长度呢？数据范围更是告诉我们这个方法的时间复杂度是足够小的，提示我们进一步思考如何操作。

枚举得到 $\operatorname{mex}$ 的值后如何计算其最大区间长度呢？通过观察容易发现，如果在一个子区间中没有 $a_i=b_i=x$ 的情况出现，那么其 $mex$ 值一定小于等于 $x$。

这是很好理解的，可以将 $a_i=b_i=x$ 看成一个针对 $x$ 的屏障，如果没有屏障的话，我们就可以在选择时用在 $a_i$ 与 $b_i$ 之间来回“走位”的方法避开所有的 $x$，从而让它成为 $\operatorname{mex}$ 的值，当然前提是没有比 $x$ 更小的可行解。

那么我们就可以记录 $x$ 为任意值时的屏障。这不会超时，因为屏障最多就 $n$ 个。屏障会把整个区间分成若干份，这些分出来的子区间的最大长度就是 $r-l+1$ 的最大值了，然后再减去 $\operatorname{mex}$ 即可。

但是有个问题，就如我们刚才所说，$\operatorname{mex}$ 的值为 $x$ 的前提是没有更好的可行解，所以这样算出来的值不一定是区间真实的值。而这其实是杞人忧天了，因为如果有更好的解的话，也一定会被枚举到的，并且虚假的值一定小于真实答案，所以对答案不造成影响，硬着头皮算就行了。

code

#include<bits/stdc++.h>
#define N 1000005
#define ll long long
using namespace std;

int n,a[N],ans=-1e9;
vector<int> pos[N];

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1,b;i<=n;i++){
		b=read();
		if(b==a[i])pos[b].push_back(i); //记录x=b时的屏障的位置
	}
	for(int i=0;i<=n;i++){
		pos[i].push_back(n+1); //对所有的x在区间末尾加一个屏障，方便计算
		for(int j=0,before=1;j<pos[i].size();j++){
			ans=max(ans,pos[i][j]-before-i);
			before=pos[i][j]+1;
		}
	}
	cout<<ans;
	return 0;
}