MEX vs MED

Created by LXC on Fri Oct 27 09:11:39 2023

https://codeforces.com/problemset/problem/1744/F

ranting: 2000

tag: math, two pointers

problem

给出一个0到n-1的排列p，求有多少子区间$[l,r]$满足$mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)$

mex表示区间内没有出现的最小非负数整数。

med表示区间内整数排序后的第$\left \lfloor{ \frac{|S| + 1}{2} } \right \rfloor$个数，$|S|$是区间内整数的个数。

solution

考虑不同mex值的贡献

当mex至少为i时，至少包含了0到i-1在区间中。设0到i-1中最小出现位置为L，最大出现位置为R。

设$pos_i$为i的位置，不妨设$pos_i < L$

从$pos_i+1$到L位置的每个数都是大于i的所以添加后不会影响mex的值，对于mex为i的情况下med小于mex的最大区间为2*i。

遍历从$pos_i+1$到L位置的每个数作为左端点，计算合法区间的右端点的个数。即为mex=i的贡献。

我们将所有不同mex的贡献累计就是答案。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<int> a(n), p(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        p[a[i]] = i;
    }
    int l = p[0], r = p[0];  // l和r为mex为i，0到i-1中最小位置和最大位置。
    ll ans = 0;
    for (int i = 1; i < n; i++) {
        // 包含了0...i-1，mex至少为i，需要med<i，则长度为2*i以内包含l和r的区间
        if (p[i] < l) {
            for (int j = l; j > p[i]; j--) {
                // 右端最远min(j+2*i-1, n-1);
                ans += max(min(j + 2 * i - 1, n - 1) - r + 1,
                           0);  // 右端能选择的位置个数。
            }
            l = p[i];
        } else if (p[i] > r) {
            for (int j = r; j < p[i]; j++) {
                // 左端最远 max(j-2*i+1, 0)
                ans += max(l - max(j - 2 * i + 1, 0) + 1, 0);
            }
            r = p[i];
        }
    }
    // 当mex至少为n时，包含了所有数，所以l=0，r=n-1，所以还有贡献1.
    cout << ans + 1 << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}