题解：CF2146E Yet Another MEX Problem

luuia · 2025-09-22 00:22:53 · 题解

Question

定义序列 a 的权值 f(a) 为 a 当中大于 \operatorname{mex}(a) 的数的个数。

给定数组 a，现在需要你对于每个 i 求出：

Solution

设当前考虑到 i，我们记 \text{last}_{k} 表示 k 上一次出现的位置，那么当前以 i 结尾的答案就是：

这个证明是显然的，因为你要让 \operatorname{mex} = k 就需要当前不能有 k，于是下标需要从 \text{last}_{k}+1 开始。我们考虑维护 \max 后面那一堆东西，不妨设数组 g_k 表示当前 k 这个式子的值。

当我们从 i-1 转移到 i，对所有 k<a_i，因为新加入了一个 >k 的元素，所以所有 g_k 全部要加 1，然后 g_{a_i} 需要改为 0，因为当前 \text{last}_{a_i} = i。那么这时候的答案就是 \max_{k>0} g_k。

那么只需要一个支持区间加、单点改、查询全局最大值的数据结构维护一下即可，可以直接线段树。

Code

放一下赛时代码，注意这里下标全部 +1 了。

/**
 *    author: luuia
 *    created: 2025.09.21 23:08:48
**/
#include<bits/stdc++.h>
using ll = long long;
#define For(i,j,k) for(int i = j;i <= k;i++)
#define eb emplace_back
#define pll pair<ll,ll>
using namespace std;
const int N = 3e6 + 10,p = 998244353;
struct seg{ll mx[N],tg[N];
    #define ls p << 1
    #define rs p << 1 | 1
    #define md (l + r >> 1)
    #define lc ls,l,md
    #define rc rs,md + 1,r
    void psu(ll p){mx[p] = max(mx[ls],mx[rs]);}void ad(ll p,ll k){mx[p] += k,tg[p] += k;}
    void psd(ll p){if(!tg[p]) return;ad(ls,tg[p]),ad(rs,tg[p]),tg[p] = 0;}
    void upd(ll p,ll l,ll r,ll ql,ll qr,ll v){if(ql <= l && r <= qr){ad(p,v);return;}
        psd(p);if(ql <= md) upd(lc,ql,qr,v);if(qr > md) upd(rc,ql,qr,v);psu(p);
    }void upd(ll p,ll l,ll r,ll x,ll v){if(l == r){mx[p] = v,tg[p] = 0;return;}
        psd(p);x <= md ? upd(lc,x,v) : upd(rc,x,v),psu(p);
    }
}tr;void sol(){ll n;cin >> n;vector<ll> a(n + 1);For(i,1,n) cin >> a[i];
    For(i,1,n){if(a[i] > 0) tr.upd(1,1,n + 1,1,a[i],1);
        tr.upd(1,1,n + 1,a[i] + 1,0),cout << tr.mx[1] << " ";
    }cout << '\n';For(i,1,n * 4 + 100) tr.mx[i] = tr.tg[i] = 0;
}int main(){
    // freopen("input.in","r",stdin);
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    ll T;cin >> T;while(T--) sol();return 0;
}