题解：P13693 [CEOI 2025] Equal Mex

Tom17 · 2025-11-27 18:29:39 · 题解

首先可以证明划分之后的若干区间若 \textrm{mex} 相同，那么其 \textrm{mex} 等于原区间的 \textrm{mex}。

证明是简单的。若现在的 \textrm{mex} （记作 A）小于原区间的 \textrm{mex}，那么必然存在划分后至少存在一个区间包含 A，矛盾。若大于，显然不可能，因为原区间的 \textrm{mex} 在区间中没有出现，所以划分后若大于，则存在一个区间包含原区间的 \textrm{mex}，矛盾。

记询问区间的 \textrm{mex} 为 m。

先特判掉 m=1 的情况，输出 r-l+1。

贪心地去考虑，所求值就是要求，将区间划分成若干段，使得包含 1 到 m-1 所有数的区间尽可能多。暴力就是从左往右扫描，贪心选择即可。

考虑优化。

第一是如何在线快速求区间 \textrm{mex}。

可以维护一个值域主席树，主席树维护的是当前点前缀每个值最后一次出现的位置（没有则设为 0）。查询就是在 r 对应的主席树中找到第一个值使得其位置小于 l，可以用线段树二分（主席树二分）来解决。单次 O(\log V)。

第二是如何快速处理询问。

可以这样做到 O(ans \log V)。贪心反过来也是对的。考虑从 r 出发，查询该点主席树中 1 到 m-1 的最小值，跳到该位置的前一个，直到跳到 <l 的位置就结束。答案就是跳跃的次数。

发现 \textrm{mex} 大的时候直接跳。

发现 \textrm{mex} 小的时候把其预处理出来，倍增去跳即可。

具体实现时，把询问按照其 \textrm{mex} 分类然后离线。按 \textrm{mex} 扫，如果小就预处理倍增数组，大就直接跳。那样空间就不用开到 O(Bn\log V) 了。取 B=\sqrt n，可以做到 O(Bn\log n)+O(\frac n B \log n)=O(n\sqrt n \log n)。可以过前 5 档部分分。

我们充分发扬人类智慧。注意到它是区间 \textrm{mex}，真正需要倍增的不会很多个。

首先是平衡规划，可以把每个 \textrm{mex} 的区间总和和区间数量算出来，用时间复杂度比较一下用哪一个算法较快，动态选择一下。注意将比较函数的倍增的复杂度常数写大一些，以减少倍增的次数。

然后在暴力跳那一部分记忆化一下。就是拿一个数组记录一下当前在这个位置跳跃过没有，如果跳跃过就直接查表，会快很多。

实测最大点不到 1 秒，可以通过。代码已作防抄袭。

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mtp make_tuple
#define fi first
#define se second 

struct Seg
{
    int minn[N*G],ls[N*G],rs[N*G],c;

    #define mid ((l+r)>>1)

    void push_up(int x)
    {
        minn[x]=min(minn[ls[x]],minn[rs[x]]);
    }

    void change(int A,int l,int r,int& x,int ox,int v)
    {
        x=++c;
        if(l==r) return minn[x]=v,void();
        ls[x]=ls[ox],rs[x]=rs[ox];
        if(A<=mid) change(A,l,mid,ls[x],ls[ox],v);
        else change(A,mid+1,r,rs[x],rs[ox],v);
        push_up(x);
    }

    int query(int A,int B,int l,int r,int x)
    {
        if(A<=l&&r<=B) return minn[x];
        if(B<=mid) return query(A,B,l,mid,ls[x]);
        if(A>=mid+1) return query(A,B,mid+1,r,rs[x]);
        return min(query(A,B,l,mid,ls[x]),query(A,B,mid+1,r,rs[x]));
    }

    int query_bs(int l,int r,int x,int v)
    {
        if(l==r) return l;
        if(minn[ls[x]]<v) return query_bs(l,mid,ls[x],v);
        else return query_bs(mid+1,r,rs[x],v);
    }

    #undef mid
}S;

int n,q,pos[N];

int get_mex(int oril,int orir)
{
    return S.query_bs_(1,V,pos[orir],oril);
}

vi memq[N];
LL sumlth[N],sumcnt[N];

int arr[N],ans[N],st[N][22];

void calc1(int p)
{
    rep(i,1,n)
    {
        int now=0;
        if(p==1) now=i-1;
        else now=S.query(1,p-1,1,V,pos[i])-1;
        st[i][0]=now;
    }
    st[0][0]=-1;
    rep(j,1,20)
    {
        rep(i,0,n)
        {
            if(st[i][j-1]==-1) st[i][j]=-1;
            else st[i][j]=st[st[i][j-1]][j-1];
        }
    }
    for(auto id:memq[p])
    {
        int l=z[id].l,r=z[id].r;
        int nowans=0;
        per(j,20,0)
        {
            if(st[r][j]+1>=l)
            {
                nowans+=(1<<j);
                r=st[r][j];
            }
        }
        ans[id]=nowans;
    }
}

int tt[N],memmex[N];

void calc2(int p)
{
    for(auto id:memq[p])
    {
        int l=z[id].l,r=z[id].r;
        if(p==1)
        {
            ans[id]=r-l+1;
            continue;
        }
        int nowans=0;
        while(true)
        {
            int nex=0;
            if(tt[r]==p) nex=memmex[r];
            else
            {
                tt[r]=p;
                memmex[r]=S.query(1,p-1,1,V,pos[r]);
                nex=memmex[r];
            }
            if(nex>=l)
            {
                ++nowans;
                r=nex-1;
            }
            else
            {
                break;
            }
        }
        ans[id]=nowans;
    }
}

std::vector<int> solve(int kn, std::vector<int>& v,int kq,std::vector<std::pair<int, int>>& queries)
{
    n=kn,q=kq;
    rep(i,1,n) arr[i]=v[i-1];
    rep(i,1,n)
    {
        S.change_(arr[i],1,V,pos[i],pos[i-1],i);
    }
    rep(lol,1,q)
    {
        int l,r;
        tie(l,r)=queries[lol-1];
        int mex=get_mex_(l,r);
        z[lol]=node(l,r,mex);
        memq[mex].eb(lol);
        sumlth[mex]+=r-l+1;
        ++sumcnt[mex];
    }

    int nlogn=n*int(log2(n)+1);
    int logn=int(log2(n)+1);
    LL CNT=0;
    rep(p,1,V)
    {
        sumlth[p]/=p;
        if(p!=1&&1ll*sumlth[p]+n>4ll*nlogn+(LL)2ll*sumcnt[p]*22)
        {
            calc1(p);
        }
        else
        {
            calc2(p);
        }
    }
    vi vtans;
    rep(lol,1,q)
    {
        vtans.eb(ans[lol]);
    }
    return vtans;
}