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

· · 题解

有关 \operatorname{mex} 的问题，0 这个东西都比较重要。

我们考虑两种情况：\operatorname{mex}(l, r) = \operatorname{cmin}(l, r) = 0 和 \operatorname{mex}(l, r) = \operatorname{cmin}(l, r) \not= 0 的情况

先考虑 \operatorname{mex}(l, r) = \operatorname{cmin}(l, r) = 0 的情况，对于这个情况，你考虑 0 在哪里出现。

如果 0 出现在 [1,l-1] 或者 [r+1,n] 里面，那么 \operatorname{cmin}(l, r) = 0，所以你要 \operatorname{mex}(l, r) = 0，那就是 [l, r] 里面的所有数都必须为正数。

所以我们得到第一部分思路，如果这个数组里面有 0，那就考虑枚举每个非 0 的位置 i，对于这个 i 找最远的 j 使得 i \sim j 中的所有数非负，显然可以二分 ST 表把这部分变成 O(n \log n)。

接下来考虑 \operatorname{mex}(l, r) = \operatorname{cmin}(l, r) \not= 0 的情况，这个时候我们可以枚举 \operatorname{mex}(l, r) 的值，对于每个值 k，你外面不能有 \lt k 的值，所以考虑包含 0 \sim k - 1 的极长区间 [l_k, r_k]，你需要没有任意一个 k 在这个区间里面，然后你再考虑找 k 在 l_k 左边第一个出现的位置 lp，k 在 r_k 右边第一个出现的位置 rp，你发现在必然选定 [l_k, r_k] 的情况下，我们左端点可以额外延伸到 lp + 1，右端点可以延伸到 rp - 1，产生 (l_k - lp) \times (rp - r_k) 的贡献。

你考虑记每个 a_i 在哪些位置出现，每次二分找一下就行。对于极长区间你直接记一下每个数第一次和最后一次出现的位置就可以了，而 a_i 的位置你直接开个 vector 存就可以了。

时间复杂度 O(n \log n)，代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[200005],mn[200005][20],fi[200005],se[200005];
vector<ll> p[200005];
ll qmn(ll l,ll r){
    ll siz=r-l+1;
    ll p=log2(siz);
    return min(mn[l][p],mn[r-(1<<p)+1][p]);
}
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++) cin>>a[i],mn[i][0]=a[i],p[a[i]].push_back(i);
    for(ll j=1;j<20;j++){
        for(ll i=1;i+(1ll<<j)-1<=n;i++){
            mn[i][j]=min(mn[i][j-1],mn[i+(1ll<<j-1)][j-1]);
        }
    }
    ll cnt0=0,ans=0;
    for(ll i=1;i<=n;i++) cnt0+=(a[i]==0);
    if(cnt0){
        for(ll i=1;i<=n;i++){
            if(a[i]==0) continue;
            ll l=i,r=n,res=l;
            while(l<=r){
                ll md=(l+r)>>1;
                if(qmn(i,md)>0) l=md+1,res=md;
                else r=md-1;
            }
            ans+=res-i+1;
        }
    }
    for(ll i=1;i<=n;i++){
        if(fi[a[i]]) continue;
        fi[a[i]]=i;
    }
    for(ll i=n;i;i--){
        if(se[a[i]]) continue;
        se[a[i]]=i;
    }
    ll l=1e18,r=-1e18;
    for(ll i=1;i<=200000;i++){
        if(!p[i].size()) continue;
        l=min(l,fi[i-1]),r=max(r,se[i-1]);
        auto itl=lower_bound(p[i].begin(),p[i].end(),l);
        if(itl!=p[i].end()&&*itl<=r) continue;
        ll ls=(itl==p[i].begin()?0:*prev(itl));
        auto itr=upper_bound(p[i].begin(),p[i].end(),r);
        ll rs=(itr==p[i].end()?n+1:(*itr));
        ans+=(l-ls)*(rs-r);
    }
    cout<<ans<<endl;
}