CF 1699C The Third Problem

標籤： cf

有一个 $0..n-1$ 的排列 $a_i$。求有多少个排列 $b_i$ st 每一个 $[l, r]$，有 $\mathrm{MEX}_{i \in [l, r]} \left\{a_i\right\} = \mathrm{MEX}_{i \in [l, r]}\left\{b_i\right\}$。

令 $pos_i$ 表示 $i$ 在排列 $a$ 中的位置。考虑枚举 $\mathrm{MEX}_{j \in [l, r]} \left\{a_j\right\}$ 的值。如果 $\mathrm{MEX}_{j \in [l, r]}\left\{a_j\right\} = i$ 则 $a_{l..r}$ 一定包含了 $0..i-1$ 的所有值，因此这个 $l$，$r$ 应当满足 $l \le \min_{j \in [0, i)} \left\{pos_j\right\}$ 且 $r \ge \mathrm{MEX}_{j \in [0, i)} \left\{pos_j\right\}$。同时，为了保证 $b$ 的 $\mathrm{MEX}$ 与 $a$ 相同，对于值 $i$，如果 $l \le pos_i \le r$，则在 $b$ 中，$i$ 可以放在 $[l, r]$ 的任意一个位置，否则必须放在与 $a$ 相同的位置。

void solve()
{
    int n;
    scanf("%d", &n);
    std::vector<int> a(n);
    for (auto &i : a) scanf("%d", &i);
    std::vector<int> pos(n);
    for (int i = 0; i < n; i++)
        pos[a[i]] = i;
    int l = pos[0], r = pos[0];
    long long ans = 1;
    for (int i = 1; i < n; i++)
    {
        if (l <= pos[i] && pos[i] <= r) ans = ans * (r - l + 1 - i) % MODN; // 注意减去已经安排好位置的 i 个元素.
        l = std::min(l, pos[i]);
        r = std::max(r, pos[i]);
    }
    printf("%lld\n", ans);
}