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

· · 题解

考虑枚举 i，统计 \text{mex}(l,r)=\text{cmin}(l,r)=i 的 (l,r) 数量。\ 首先，这个区间一定要包含 a_j<i 的所有 j。设 x=\min_{a_j<i} j,y=\max_{a_j<i} j，则就能得出第一个条件：

l\le x,y\le r

随后，i 一定不能在 [l,r] 中出现，所以若存在 x\le j\le y,a_j=i 则一定没有。判掉无解后，设 L 为最大的 j 使得 j<x,a_j=i，R 为最大的 j 使得 j>y,a_j=i，就可以得出第二个条件：

L<l,r<R

综上，总方案数就是

(x-L)(R-y)

实现的时候储存每个 i 出现的位置，就可以用二分较为方便地查询 x,y,L,R 了。\ 最后注意特判 i=0 的情况，这种情况就要求 [l,r] 中间不存在 0。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,ans;
vector<int>p[N];
#define cnt(x) (x)*(x+1)/2
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    cin>>n;
    for(int i=0;i<N;i++) p[i].push_back(0);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%lld",&x);
        p[x].push_back(i);
    }
    for(int i=0;i<N;i++) p[i].push_back(n+1);
    if(p[0].size()!=2){//特判不存在
        for(int i=1;i<p[0].size();i++) ans+=cnt(p[0][i]-p[0][i-1]-1);//i=0 的情况
        int l=n+1,r=0;//此处的 l,r 为上文的 x,y
        for(int c=1;c<N;c++){
            if(p[c].size()==2) break ;//特判不存在
            l=min(l,p[c-1][1]);
            r=max(r,p[c-1][p[c-1].size()-2]);
            if(*lower_bound(p[c].begin(),p[c].end(),l)<=r) continue ;
            int L=p[c][lower_bound(p[c].begin(),p[c].end(),l)-p[c].begin()-1];
            int R=p[c][upper_bound(p[c].begin(),p[c].end(),r)-p[c].begin()];
            ans+=(l-L)*(R-r);
        }
    }
    cout<<ans<<'\n';
    return 0;
}/*
*/