CF1223F Stack Exterminable Arrays 题解

分析

接着这个说。

现在我们需要优化 \(\mathit{nxt}_{i}\)。重新定义一下，\(\mathit{nxt}_{i,j}\) 表示在后 \(i\) 个数中，\(j\) 第一次出现的位置，且 \([i+1,\mathit{nxt}_{i+1,a_i}-1]\) 是一个合法串。这玩意很像一个 DP，所以完全可以按照 DP 的转移思路转移：\(\mathit{nxt}_{i,j}=\min(i|a_i=j,\mathit{nxt}_{\mathit{nxt}_{i,a_i}+1,j})\)。但这个转移的前提是在 \(\mathit{nxt}_{i+1}\) 中存在 \(1 \le \mathit{nxt}_{i+1,a_i} \le n\)。因为只有在这种情况，我们才能保证转移后的 \(\mathit{nxt}\) 合法。

对于转移，直接交换再把 \(a_i\) 更新就能做到 \(O(1)\) 了。正确性可以自己想想。

这题的话，就是把字符串变成数字，复杂度 \(O(n \log n)\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline

const int N=3e5+10;
int n,a[N];
int f[N];
map<int,int> nxt[N];

il void solve(){
    cin>>n;
    for(re int i=1;i<=n;++i) cin>>a[i],f[i]=0,nxt[i].clear();
    nxt[n+1].clear(),f[n+1]=0;
    int ans=0;
    for(re int i=n;i>=1;--i){
        if(nxt[i+1].count(a[i])){
            f[i]=f[nxt[i+1][a[i]]+1]+1;
            swap(nxt[i],nxt[nxt[i+1][a[i]]+1]);
        }
        nxt[i][a[i]]=i;
    }
    for(re int i=1;i<=n;++i) ans+=f[i];
    cout<<ans<<"\n"; 
}

signed main(){
    int t;cin>>t;while(t--)
    solve();
    return 0;
}