CF2146E 题解

Danielcdo · 2025-09-22 11:24:39 · 题解

观察

首先需要根据题面和 \operatorname{mex} 的性质得出一个重要结论：对于一个数组 b，满足\sum_{i=1}^{n} (b_i>\operatorname{mex}(b))=\max_{x}^{b_i\ne x} \sum_{i=1}^{n} (b_i>x)，因为满足 b_i>x 的位置数量越大，x 越小，而 \operatorname{mex} 的定义本身就是最小，所以可以这样放宽条件。

设计

得出这个结论后，我们就可以拿一个数组 c 维护 x 的贡献，设当前右端点 r 约束下，x 最后一个出现的位置为 p，那么要使 x 不存在于 [l,r] 中，即 l>p，又要使这个区域内大于 x 的 a_i 数量尽量多，所以 l=p+1，因此 c_x 的值就是 [p+1,r] 区间内大于 x 的 a[i] 的数量，而对于 r 的答案就是 c 数组的最大值。

实现

考虑如何维护 c 数组，当我们 r 向后移动 1 次后，加入新的元素 a_r，对于 c 的每一个位置 i：

具体操作为区间加，单点归零，可以用线段树动态维护修改、查询。

代码

#include <iostream>
#include <cstdio>
using namespace std;
int read()
{
    char c=getchar();
    int f=1,x=0;
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    return x*f;
}
void print(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int t,n,a[300005];
struct Segment_Tree
{
    int tr[1200005],tag[1200005];
    void build(int p,int s,int t)
    {
        tr[p]=tag[p]=0;
        if(s==t) return;
        int mid=(s+t)>>1;
        build(p<<1,s,mid);
        build(p<<1|1,mid+1,t);
    }
    void pushdown(int p)
    {
        tr[p<<1]+=tag[p];
        tr[p<<1|1]+=tag[p];
        tag[p<<1]+=tag[p];
        tag[p<<1|1]+=tag[p];
        tag[p]=0;
    }
    void update1(int p,int s,int t,int l,int r)
    {
        if(s!=t) pushdown(p);
        if(s>=l&&t<=r)
        {
            tr[p]++;
            tag[p]++;
            return;
        }
        int mid=(s+t)>>1;
        if(l<=mid) update1(p<<1,s,mid,l,r);
        if(r>mid) update1(p<<1|1,mid+1,t,l,r);
        tr[p]=max(tr[p<<1],tr[p<<1|1]);
    }
    void update2(int p,int s,int t,int x)
    {
        if(s==t)
        {
            tr[p]=0;
            return;
        }
        pushdown(p);
        int mid=(s+t)>>1;
        if(x<=mid) update2(p<<1,s,mid,x);
        else update2(p<<1|1,mid+1,t,x);
        tr[p]=max(tr[p<<1],tr[p<<1|1]);
    }
}tree;
int main()
{
    t=read();
    while(t--)
    {
        n=read();
        for(int i=1;i<=n;i++) a[i]=read();
        tree.build(1,0,n);
        for(int i=1;i<=n;i++)
        {
            if(a[i]) tree.update1(1,0,n,0,a[i]-1);
            tree.update2(1,0,n,a[i]);
            print(tree.tr[1]);
            putchar(' ');
        }
        putchar('\n');
    }
    return 0;
}