题解：P9970 [THUPC 2024 初赛] 套娃

· · 题解

P9970 套娃

前置知识

  1. 主席树（动态开点权值线段树）

  2. set 维护 \text{mex}

在线区间 \text{mex}

考虑确定右端点后 \text{mex} 咋求。设 i 出现最晚的位置记为 p_i，若没有则为 0，权值线段树单点赋值实现；询问时，满足 0\le i\le mex 的 i 一定有 p_i\ge l，可以转化为 \min_{i=0}^{mex-1} p_i\ge l，权值线段树上二分求出答案。至于右端点不同的情况，主席树每次加链就行了。

极小 \text{mex} 区间

设 [l,r] 的 \text{mex}=x，定义满足 [l,r] 不存在另一个子区间 [L,R] 的 \text{mex}=x 的 [l,r] 为极小 x-\text{mex} 区间。

结论是极小 \text{mex} 区间的个数为 O(n) 级别的，简单证明我不会证。

那么如何求呢？对于 x-\text{mex} 找左边第一个 a_L=x，右边第一个 a_R=x（若没有则不做）。接下来求 [L,r] 的 y=\text{mex} 并放进 y-\text{mex} 中；求 [l,R] 的 y=\text{mex} 并放进 y-\text{mex} 中。

每次要进行去重，即只保留小区间，包含小区间的大区间删除。

答案

对于每个极小 x-\text{mex} 区间找左边第一个 a_L=x，右边第一个 a_R=x（和前面不一样，若没有则赋为边界值 0/n+1）。那么区间长度为 r-l+1\sim R-L-1 会有 \text{mex}=x 的区间。

之后用扫描线 set 动态维护 \text{mex} 就做完了。

注意在 \text{mex}=x 时可能会有 l1\sim r1|l2\sim r2(l1\le l2\le r1\le l2)，即有重区，直接扫会出问题。因此可以用 ODT 区间推平或区间去重做。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100000 , M = 20 * N + 5 , inf = 1e9;
int cc , siz , st[N + 5];
struct STree
{
    int idx = 0;
    int lc[M] = {0} , rc[M] = {0} , d[M] = {0};
    void push_up (int p) { d[p] = min (d[lc[p]] , d[rc[p]]); }
    void bld (int &p , int s = 1 , int t = siz)
    {
        p = ++ idx;
        if (s == t) return ;
        int mid = s + t >> 1;
        bld (lc[p] , s , mid);
        bld (rc[p] , mid + 1 , t);
    }
    void add (int &p , int q , int ps , int c , int s = 1 , int t = siz)
    {
        p = ++ idx;
        if (s == t)
        {
            d[p] = c;
            return;
        }
        int m = s + t >> 1;
        if (ps <= m) rc[p] = rc[q] , add (lc[p] , lc[q] , ps , c , s , m);
        else lc[p] = lc[q] , add (rc[p] , rc[q] , ps , c , m + 1 , t);
        push_up (p);
    }
    int qry (int p , int w , int s = 1 , int t = siz)
    {
        if (s == t)
            return s - 1;
        int m = s + t >> 1;

        if (d[lc[p]] >= w) return qry (rc[p] , w , m + 1 , t);
        else return qry (lc[p] , w , s , m);
    }
} T;
int n , x;
vector <pair <int , int> > mex[N + 5] , ln[N + 5];
vector <int> s[N + 5] , g[N + 5];
bool cmp (pair <int , int> x , pair <int , int> y)
{
    if (x.first != y.first) return x.first > y.first;
    return x.second < y.second;
}
bool cmp2 (pair <int , int> x , pair <int , int> y)
{
    if (x.first != y.first) return x.first < y.first;
    return x.second > y.second;
}
signed main ()
{
    ios::sync_with_stdio (0) , cin.tie (0) , cout.tie (0);
    T.d[0] = inf;
    cin >> n;
    siz = n + 3;
    T.bld (st[0]); 
    for (int i = 0;i <= n + 1;i ++) s[i].push_back (0);
    for (int i = 1;i <= n;i ++)
    {
        cin >> x;
        T.add (st[i] , st[i - 1] , x + 1 , i);
        if (!x) mex[1].push_back ({i , i});
        else mex[0].push_back ({i , i});
        s[x].push_back (i);
    }
    for (int i = 0;i <= n + 1;i ++) s[i].push_back (n + 1);
    for (int i = 0;i <= n;i ++)
    {
        sort (mex[i].begin () , mex[i].end () , cmp);
        vector <pair <int , int> > now;
        int mn = 1e9;
        for (auto w : mex[i])
            if (mn > w.second)
                now.push_back (w) , mn = w.second;
        reverse (now.begin () , now.end ());
        mex[i] = now;
        for (auto w : mex[i])
        {
            int l = w.first , r = w.second;
            int L = *(lower_bound (s[i].begin () , s[i].end () , l) - 1) , R = *upper_bound (s[i].begin () , s[i].end () , r);
            if (L)
            {
                int _mex = T.qry (st[r] , L);
                mex[_mex].push_back ({L , r});
            }
            if (R <= n)
            {
                int _mex = T.qry (st[R] , l);
                mex[_mex].push_back ({l , R});
            }
        }
    }
    multiset <int> S;
    for (int i = 0;i <= n + 1;i ++)
    {
        S.insert (i);
        for (auto w : mex[i])
        {
            int l = w.first , r = w.second;
            int L = *(lower_bound (s[i].begin () , s[i].end () , l) - 1) , R = *upper_bound (s[i].begin () , s[i].end () , r);
            ln[i].push_back ({r - l + 1 , R - L - 1});
        }
    }
    S.insert (n + 2);
    for (int i = 0;i <= n;i ++)
    {
        int mx = 0;
        vector <pair <int , int> > now;
        sort (ln[i].begin () , ln[i].end () , cmp2);
        for (auto w : ln[i])
            if (mx < w.second)
                mx = w.second , now.push_back (w);
        int len = now.size ();
        for (int i = 1;i < len;i ++)
            now[i].first = max (now[i].first , now[i - 1].second + 1);
        for (auto w : now)
            g[w.first].push_back (i + 1) , g[w.second + 1].push_back (-i - 1);
    }
    for (int i = 1;i <= n;i ++)
    {
        for (int w : g[i])
        {
            if (w < 0) S.insert (-w - 1);
            else S.erase (w - 1);
        }
        cout << *S.begin () << ' ';
    }
    return 0;
}