CF1744F MEX vs MED Solution

看到 \(\text{mex}>\text{med}\)，想到一定满足 \([0,\text{med}]\) 都在区间内出现过。

那么考虑枚举 \(\text{med}\)，对于每一个 \(\text{med}\) 计算答案。

每次加入一个新元素，如果它原本不在区间内，就把左端点 / 右端点设为它。

考虑 \(\text{med}\) 的定义，分两种情况。

1. 区间内比它小的有 \(x\) 个，比它大的也有 \(x\) 个。

因为按照我们的做法，\([0,\text{med}-1]\) 此时都被包含在区间内，即 \(x\) 确定。我们只需要枚举左侧放多少个比它大的，然后判断右侧是否放得下就可以了。

假设当前区间为 \([l,r]\)。

那么左侧最多放 \(l-1\) 个，右侧最多放 \(n-r\) 个，总共还需要放 \(\text{med}-p\) 个。

此处 \(p\) 表示 \([l,r]\) 内 \(>\text{med}\) 的数。

解不等式即可。

2. 区间内比它小的有 \(x\) 个，比它大的也有 \(x+1\) 个。

同理。

因为数组开小了，吃了一发罚时。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 10;
int t, n, a[N], pos[N];

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    cin >> t; while (t--) {
        cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i], pos[a[i]] = i;
        int res = 1, cnt = 0; int l = pos[0], r = pos[0];
        if (l > 1) ++res; if (r < n) ++res;
        for (int i = 1; i < n; ++i) {
            int cur = pos[i];
            if (cur < l) {
                for (int j = l - 1; j >= cur; --j)
                    if (a[j] > i) ++cnt;
                l = cur;
            } else if (cur > r) {
                for (int j = r + 1; j <= cur; ++j)
                    if (a[j] > i) ++cnt;
                r = cur;
            } else --cnt;
            int Min = r - l - cnt, Max = cnt;
            int sum = Min; sum -= Max;
            int lef = max(0ll, sum - n + r), rig = min(l - 1, sum);
            res += max(rig - lef + 1, 0ll);
            sum = Min + 1; sum -= Max;
            lef = max(0ll, sum - n + r), rig = min(l - 1, sum);
            res += max(rig - lef + 1, 0ll);
        }
        cout << res << endl;
    }
    return 0;
}