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

· · 题解

关于某人在一道黄题上 all in 两个小时……

正解

考虑我们要找的区间 [l,r] 应当满足什么条件：设 \operatorname{mex}(l,r)=\operatorname{cmin}(l,r)=k，则在 [l,r] 中，0 \sim k-1 一定都要出现，k 一定不出现；在两个补区间 [1,l-1] 和 [r+1,n] 中，0 \sim k-1 不出现且 k 必须出现。

很自然会有初步想法：当前 k 的最小区间应该至少包含 0 \sim k-1 在原数组中出现的最左和最右下标，设为 [l_0,r_0]。（同时应保证其中不含 k，否则因为已经是最小区间了，所以当前答案为 0）

然后考虑如何在最小区间的基础上扩展统计答案，因为最小区间的选取同时也保证了在其补区间内不会出现 0 \sim k-1 中的数字，所以我们只要找 k 在最小区间两侧的首次出现位置 l_k 和 r_k；又因为要求区间内不含 k，所以合法答案区间的左右端点范围有 l \in (l_k,l_0], r \in [r_0,r_k)，共有 (l_0-l_k)(r_k-r_0) 个。

查找可以用二分简单实现，也可以选择每次直接遍历对应的位置数组“暴力”找，因为最小区间一直在单调扩展且每个位置只会被遍历一次。

注意：若 l_k 或 r_k 不存在，说明可以取的范围有 l \in [1,l_0], r \in [r_0,n]，为了贴合上述的答案计算形式也可以写成 l \in (0,l_0], r \in [r_0,n+1)，即 l_k=0,r_k=n+1。

根据性质，我们发现当 k 递增时，答案区间一定不会缩小，所以可以根据新的 k 的出现位置快速更新新的最小区间 [l_0,r_0]。

特殊地，当 k=0 时，合法区间中一定不存在 0，直接统计被 0 分隔的部分能组成多少连续段即可。如果 0 不存在，那么区间最小值一定不等于 \operatorname{mex}=0，无合法区间。

注意如果 k 出现了“断层”，即某一个 k 不在原数列中，那么再继续扩大区间，\operatorname{mex} 也将永远为 k，应直接退出循环，输出答案。

::::info[Code]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;

int n, a[maxn];
vector<int> pos[maxn]; // 统计每个值出现的位置

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i]; pos[a[i]].push_back(i); // 预处理位置
    }
    for(int i = 0; i <= 2e5; i ++){ 
        sort(pos[i].begin(), pos[i].end()); // 排序
    }
    if(pos[0].empty()){ // 特判
        cout << 0; return ; 
    }

    // 统计k=0的答案
    ll ans = 0;
    for(int i = 0; i < (int)pos[0].size()-1; i ++){
        int s = pos[0][i+1] - pos[0][i] - 1; // 统计非0元素个数
        ans += 1LL*s*(s+1)/2;
    }
    // 注意不要漏下[1,pos0[0]]、[pos0[sz-1],n]两个周边没有0包裹的段
    if(1 < pos[0][0]){
        ans += 1LL*pos[0][0]*(pos[0][0]-1)/2;
    }
    if(pos[0].back() < n){
        int s = n - pos[0].back();
        ans += 1LL*s*(s+1)/2;
    }

    int l0 = pos[0][0], r0 = pos[0].back();
    for(int k = 1, lk, rk; k < maxn; k ++){
        if(pos[k].empty()) break;

        // 确定lk,rk
        auto it = lower_bound(pos[k].begin(), pos[k].end(), l0);
        if(it!=pos[k].begin()) lk=*prev(it);
        else lk=0;

        it = upper_bound(pos[k].begin(), pos[k].end(), r0);
        if(it!=pos[k].end()) rk=*it;
        else rk=n+1;

        // 检查[l0,r0]中是否存在k
        it = lower_bound(pos[k].begin(), pos[k].end(), l0);
        if(it==pos[k].end() || *it>r0){
            ans += 1LL*(l0-lk)*(rk-r0);
        }

        // 扩展l0,r0
        l0 = min(l0, pos[k][0]);
        r0 = max(r0, pos[k].back());
    }

    cout << ans << '\n';
}

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

::::