射命丸文的取材之旅 题解

retep · 2022-07-25 00:05:41 · 题解

题目简述

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

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

其中 \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;
}