P8087 『JROI-5』Interval

· · 题解

官方题解。

B

考虑改写条件，根据整数的离散性，容易写为

f_{r-l+1}\leq \operatorname{Mex}_{l,r}-1

观察到 \operatorname{Mex} 存在单调性。如何理解该单调性呢？假设 \operatorname{Mex}_{l_0,r_0}=x，那么对于任意的 p>l_0-r_0+1，都存在至少一个长度为 p 的区间 \left[l_1,r_1\right] 使得 \operatorname{Mex}_{l_1,r_1}\geq x.

显然这对我们极具启发意义，与其枚举区间长度，不如枚举 \operatorname{Mex}，对于每个 \operatorname{Mex}=x，我们都可以求出最短的区间 \left[l_0,r_0\right] 使得 \operatorname{Mex}_{l_0,r_0}-1=f_{r-l+1}，那么只要 r_0-l_0+1\leq r-l+1，区间 \left[l,r\right] 就是合法的。

那么如何 \mathcal{O}\left(1\right) 求出 \left[l_0,r_0\right] 呢，容易发现，如果 \operatorname{Mex}_{l_0,r_0} \geq x，那么1\sim x-1 必须在 \left[l_0,r_0\right] 出现，所以，我们用数组记录下每个数出现的位置，做前缀 \max,\min 即可快速求解。

for(int i = 1; i <= n; i ++)
    pos[a[i]] = i;  
_min[0] = n + 1;
for(int i = 1; i <= n; i ++){
    _max[i] = max(_max[i - 1], pos[i]);
    _min[i] = min(_min[i - 1], pos[i]);
}

之后就可以快速求解满足 \operatorname{Mex} = i + 1 的最短区间，我们不妨把它设为 g\left[i\right].

for(int i = 1; i <= n; i ++)
    g[i] = _max[i] - _min[i] + 1;

然后枚举区间长度判断即可解决。

int ans = 0;
for(int i = 1; i <= n; i ++){
    if(f[i] <= n && g[f[i]] <= i){
        ans = i;
        break; 
    } 
}

综合时间复杂度 \mathcal{O}\left(n\right) 的。

部分分分别是给 \mathcal{O}\left(n^3\right),\mathcal{O}\left(n^2\right),\mathcal{O}\left(n\log n\right) 的。