题目详解

问题重述

定义数组 $b$ 的权重为： [ \text{weight}(b) = #{ i \mid b_i > \text{MEX}(b) } ] 其中 $\text{MEX}(b)$ 是数组 $b$ 中未出现的最小非负整数。

给定数组 $a[1..n]$，对每个位置 $i$，求所有以 $i$ 结尾的子数组的最大权重： [ \text{ans}[i] = \max_{1 \le l \le i} w(l, i) ] 其中 $w(l, i)$ 是子数组 $a[l..i]$ 的权重。

算法思路

关键观察

设子数组的 MEX 值为 $m$，则权重为子数组中严格大于 $m$ 的元素个数。

当右端点 $i$ 固定时，随着左端点 $l$ 从 $i$ 向左移动，MEX 值会发生变化，但变化次数有限（MEX 值单调不减，且不超过 $n$）。

我们可以维护一个数据结构，对每个可能的 MEX 值 $m$，记录当前右端点下 MEX 为 $m$ 的子数组的最大权重。

动态维护

当右端点从 $i-1$ 移动到 $i$，加入新元素 $a[i]$ 时：

1. 对所有 $m \le a[i]$：
   如果 $m < a[i]$，则新加入的元素 $a[i] > m$，所以权重增加 $1$；
   如果 $m = a[i]$，则新元素等于 MEX，不满足严格大于，权重不变。

2. 对所有 $m > a[i]$：
   新元素小于 MEX，不影响权重，但 MEX 值可能改变（如果 $a[i]$ 是之前缺失的，MEX 会变大）。

线段树设计

代码中用线段树维护 $f(m)$ 表示 MEX 值为 $m$ 的子数组的最大权重：

• 线段树下标范围 $[0, n]$，对应 MEX 的可能取值。
• 每个节点存储当前区间内所有 $f(m)$ 的最大值。
• 支持两种操作：
  • 区间加：将 $[0, a[i]]$ 范围内的所有 $f(m)$ 加 $1$
  • 单点赋值：将位置 $a[i]$ 的值设为负无穷（表示这些子数组不合法）

为什么这样正确？

1. 区间加 $[0, a[i]]$：
   对所有 $m \le a[i]$，新元素 $a[i]$ 是否大于 $m$？

   • 若 $m < a[i]$，确实 $a[i] > m$，应加 $1$ ✓
   • 若 $m = a[i]$，$a[i] = m$，不应加 $1$ ✗

   所以我们先统一加 $1$，再通过单点赋值把 $m = a[i]$ 的位置设为负无穷，这样在取最大值时自然排除了这些不合法的子数组。

2. 单点赋值负无穷：
   表示以当前右端点结尾、MEX 恰好为 $a[i]$ 的子数组，因为新加入的元素等于 MEX，所以这些子数组的权重不应该被计入。

3. 线段树根节点存储最大值：
   每次操作后，根节点的值就是 $\max_{m} f(m)$，即所有以 $i$ 结尾的子数组的最大权重。

完整代码

#include<bits/stdc++.h>
using namespace std;
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)

int n;
int a[300005];

struct ds {
    int seg[1200005], tag[1200005];
    
    // 建树
    void build(int l, int r, int p) {
        seg[p] = tag[p] = 0;
        if(l == r) return;
        int m = (l + r) >> 1;
        build(l, m, p*2+1);
        build(m+1, r, p*2+2);
    }
    
    // 区间加 [l, r]
    void update(int l, int r, int s, int t, int p) {
        if(l <= s && t <= r) {
            ++seg[p];
            ++tag[p];
            return;
        }
        int m = (s + t) >> 1;
        if(m >= l) update(l, r, s, m, p*2+1);
        if(m < r) update(l, r, m+1, t, p*2+2);
        seg[p] = max(seg[p*2+1], seg[p*2+2]) + tag[p];
    }
    
    // 单点赋值负无穷（实际上是 -val，val 是累加标记）
    void point(int pos, int l, int r, int p, int val = 0) {
        if(l == r) {
            seg[p] = -val;  // 设为负无穷（实际是负的当前累加值）
            return;
        }
        int m = (l + r) >> 1;
        val += tag[p];
        if(m >= pos) point(pos, l, m, p*2+1, val);
        else point(pos, m+1, r, p*2+2, val);
        seg[p] = max(seg[p*2+1], seg[p*2+2]) + tag[p];
    }
} seg;

void Main() {
    cin >> n;
    REP(i, 0, n) cin >> a[i];
    
    seg.build(0, n, 0);  // 构建线段树
    
    REP(i, 0, n) {
        // 步骤1：对所有 MEX <= a[i] 的权重加 1
        seg.update(0, a[i], 0, n, 0);
        
        // 步骤2：将 MEX = a[i] 的权重设为负无穷
        seg.point(a[i], 0, n, 0);
        
        // 输出当前最大值
        cout << seg.seg[0] << ' ';
    }
    cout << '\n';
}

void TC() {
    int tc = 1;
    cin >> tc;
    while(tc--) {
        Main();
        cout.flush();
    }
}

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    TC();
    return 0;
}

算法复杂度

• 时间复杂度：$O(n \log n)$，每个元素执行一次区间加和一次单点操作，线段树操作均为 $O(\log n)$。
• 空间复杂度：$O(n)$，线段树大小约为 $4 \times n$。

样例验证

以第二个样例 $a = [2, 0, 3, 0, 1]$ 为例：

输出：1 1 2 2 1，与题目一致。

总结

本题的核心技巧：

1. 将问题转化为对每个可能的 MEX 值维护最大权重
2. 利用线段树支持区间加和单点修改
3. 通过"先加后清空"的技巧处理边界情况

这种方法充分利用了 MEX 值范围有限（$0$ 到 $n$）的特点，将原问题优雅地转化为了线段树维护区间最大值的问题。