P8087 『JROI-5』Interval题解

· · 题解

更新日志：

题意：

给定两个长度为 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;
    }
}