题解 CF1223F 【Stack Exterminable Arrays】

meyi · 2023-10-22 12:50:48 · 题解

提供一种码量极小的 O(n) 确定性做法。

首先转化一下题意，[l,r] 合法等价于 [1,l-1] 的栈的状态与 [1,r] 的栈的状态完全相同，所以 i 对答案的贡献就是有多少个 j 满足 0\leq j<i 且 [1,j] 与 [1,i] 的栈的状态相同，特别的，我们记 [1,0] 的栈的状态为 \varnothing。

很显然可以哈希来求这个，但是没必要。将栈看做一个字符串，考虑我们每次 push 或者 pop 某个数的本质，其实是在字典树上移动到了当前点的儿子或者父亲，对答案的贡献也就是有多少个字符串以当前点为末尾。

由于 |\sum| 与 n 同阶，故使用 unordered_map 来记录儿子，时间复杂度 O(n)。

代码：

#include<bits/stdc++.h>
using namespace std;
struct trie{
    trie *fa;
    int siz;
    unordered_map<int,trie*>son;
    inline trie(trie *f){fa=f,siz=0;}
};
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        vector<int>a(n);
        for(int &i:a)scanf("%d",&i);
        long long ans=0;
        trie *rt=new trie(NULL);
        ++rt->siz;
        vector<int>st;
        for(int i:a){
            if(st.empty()||st.back()!=i){
                st.push_back(i);
                rt=rt->son.emplace(i,new trie(rt)).first->second;
            }
            else rt=rt->fa,st.pop_back();
            ans+=rt->siz++;
        }
        printf("%lld\n",ans);
    }
    return 0;
}