题解：P17234 [Algo Beat Contest 017 C] 交互题

wimpy_kitty · 2026-08-10 18:09:16 · 题解

首先发现没有 0 的序列必然无解，接下来逐层考虑。

考虑枚举 \operatorname{mex} 计算符合 \operatorname{mex} = i 的区间，那么必然其包含 0 到 i - 1，因为要求该区间合法，所以外面不能有 0 到 i - 1 的数字，也就是他必须包含所有的 1 到 i - 1 的所有数，那么考虑当 i 增加的时候就是双指针维护左右最长延长距离即可。

#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <vector>
#include <cmath>
#define ll long long
#define pb push_back

using namespace std;
const int N = 2e5 + 9;
ll n, a[N], book[N], lt, rt;
ll ans;
vector <ll> vec[N];

inline ll cal(ll x) {return x * (x + 1) / 2;}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i], vec[a[i]].pb(i);
    if (!vec[0].size()) return cout << 0, 0;

    int lst = 0;
    lt = n + 1; rt = 0;
    for (auto i: vec[0]) {
        ans += cal(i - 1 - lst);
        lt = min(lt, i);
        rt = max(rt, i);
        lst = i;
    }
    ans += cal(n - lst);
    for (int i = lt; i <= rt; i ++)
        book[a[i]] ++;

    ll lsum, rsum;
    for (int i = 1; i <= n; i ++) {
        if (!vec[i].size()) break;
        lsum = rsum = 0;
        if (!book[i]) {
            int l = 0, r = vec[i].size() - 1;
            while (l <= r) {
                int mid = l + r >> 1;
                if (vec[i][mid] < lt)
                    lsum = lt - vec[i][mid], l = mid + 1;
                else r = mid - 1;
            }
            if (lsum == 0) lsum = lt;
            l = 0; r = vec[i].size() - 1;
            while (l <= r) {
                int mid = l + r >> 1;
                if (vec[i][mid] > rt)
                    rsum = vec[i][mid] - rt, r = mid - 1;
                else l = mid + 1;
            }
            if (rsum == 0) rsum = n - rt + 1;
            ans += 1ll * lsum * rsum;
            // cerr << i << ' ' << lsum * rsum << endl;
        }
        while (lt > vec[i][0]) lt --, book[a[lt]] ++;
        while (rt < vec[i][vec[i].size() - 1]) rt ++, book[a[rt]] ++;
        // cerr << i << ' ' << lt << ' ' << rt << endl;
    }
    cout << ans;

    return 0;
}

很难想想这个题解有人能看懂，主要还是双指针