题解：P8087 『JROI-5』Interval

这是一道不错的思维题，赛时我的思路是逆向思维法。从长度为 $n$ 的合法区间开始判断，因为由 $f_{r - l + 1} < \rm Mex_{l,r}$可知，若让区间成为合法区间，需要使 $\rm Mex_{l,r}$ 尽可能大。所以就有了一个策略：从长度为 $n$ 的区间开始，若为合法区间则更新答案，否则去除两端的较大数，直至区间为 $1$。

而对于 $k = \rm Mex_{l,r}$ 的更新也很简单，由于逆着操作，所以一开始的值为 $n + 1$，当去除数字之后，直接更新为 $\min (k,x)$，$x$ 表示被去除的数字。

思路十分简单且清晰，那么直接给出代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 4e6 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,k,l,r,ans = INF;
int a[MAX],f[MAX];
int main ()
{
    n = read ();
    for (int i = 1;i <= n;++i) a[i] = read ();
    for (int i = 1;i <= n;++i) f[i] = read ();
    k = n + 1;//k 代表 Mex 函数的值，一开始为 n + 1
    l = 1;r = n;
    for (int i = n;i >= 1;--i)//逆向思维
    {
        if (f[i] < k) ans = min (ans,r - l + 1);//存在合法区间，答案被更新
        if (a[l] < a[r]) k = min (k,a[r--]);//右侧端较大，去除右侧的数字，同时 k 进行更新
        else k = min (k,a[l++]);//去除左端
    }
    if (ans == INF) printf ("0\n");//答案未被更新，也就是没有合法区间
    else printf ("%d\n",ans);
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}