专栏文章

题解：CF2146E Yet Another MEX Problem

lluuia
CF2146E题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mintqogc
此快照首次捕获于
2025/12/02 08:12
3 个月前
此快照最后确认于
2025/12/02 08:12
3 个月前
查看原文

Question

定义序列 aa 的权值 f(a)f(a) 为 aa 当中大于 mex⁡(a)\operatorname{mex}(a) 的数的个数。
给定数组 aa，现在需要你对于每个 ii 求出：
max⁡1≤l≤if(a[l,l+1,⋯ ,i])\max_{1 \le l \le i} f(a[l,l+1,\cdots ,i])

Solution

设当前考虑到 ii，我们记 lastk\text{last}_{k} 表示 kk 上一次出现的位置，那么当前以 ii 结尾的答案就是：
max⁡k>0∑j=lastk+1i[aj>k]\max_{k>0} \sum_{j = \text{last}_{k}+1}^i [a_j>k]
这个证明是显然的，因为你要让 mex⁡=k\operatorname{mex} = k 就需要当前不能有 kk，于是下标需要从 lastk+1\text{last}_{k}+1 开始。我们考虑维护 max⁡\max 后面那一堆东西，不妨设数组 gkg_k 表示当前 kk 这个式子的值。
当我们从 i−1i-1 转移到 ii，对所有 k<aik<a_i，因为新加入了一个 >k>k 的元素，所以所有 gkg_k 全部要加 11，然后 gaig_{a_i} 需要改为 00，因为当前 lastai=i\text{last}_{a_i} = i。那么这时候的答案就是 max⁡k>0gk\max_{k>0} g_k。
那么只需要一个支持区间加、单点改、查询全局最大值的数据结构维护一下即可，可以直接线段树。

Code

放一下赛时代码，注意这里下标全部 +1+1 了。
CPP
/**
 *    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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...