CF1223F Stack Exterminable Arrays

CCF 出的原题观摩一下。

思路

首先可以用一个 Trie 来维护。

在这里对本文中的一些变量做一下说明。

1. $p$ 表示当前维护的 Trie 中，指向的元素编号。
2. $t_i$ 表示在 Trie 中编号为 $i$ 的元素在原序列中的值。
3. $f_i$ 表示在 Trie 中编号为 $i$ 的元素在 Trie 中的父节点。
4. $v_i$ 表示在 Trie 中编号为 $i$ 被遍历的次数。

考虑每一次将一个数 $a_i$ 加入 Trie 的时候需要做什么操作。

如果当前在 Trie 中指向的节点 $t_p$ 与 $a_i$ 相等，说明可以进行合并， 那么直接将 $p$ 跳到 $f_p$ 即可；否则需要新开一个节点 $v$，接在 $p$ 的下方，并将 $p$ 更新到 $v$ 上。

然后在更新 $p$ 之后，要将 $v_p$ 加 $1$。

考虑如何统计答案。发现点 $p$ 被遍历过 $2$ 次时，答案会加 $1$；$3$ 次，答案会加 $2$；以此类推。

这是因为当 $v_p > 1$ 时，说明 $p$ 节点已经可以被合并 $v_p - 1$ 次了，所以直接加 $v_p - 1$ 即可。

注意：在代码中为了优美，将 $v_p$ 初值设为了 $-1$。

但是用普通的 Trie 显然是过不了的，因为 Trie 的空间复杂度在本题中会变为 $\Theta(n^2)$，所以直接开一个 umap 即可。

复杂度为 $\Theta(n \log n)$，实测跑得飞快。

Code

#include <bits/stdc++.h>  
#define re register  
#define ll long long  
  
using namespace std;  
  
const int N = 3e5 + 10;  
int T,n,p,idx;  
ll ans;  
int arr[N];  
  
struct node{  
    ll val;  
    int u,fa;  
    unordered_map<int,int> son;  
}tr[N];  
  
inline int read(){  
    int r = 0,w = 1;  
    char c = getchar();  
    while (c < '0' || c > '9'){  
        if (c == '-') w = -1;  
        c = getchar();  
    }  
    while (c >= '0' && c <= '9'){  
        r = (r << 3) + (r << 1) + (c ^ 48);  
        c = getchar();  
    }  
    return r * w;  
}  
  
inline void solve(){  
    ans = 0;  
    p = idx = 1;  
    n = read();  
    for (re int i = 1;i <= n;i++){  
        tr[i].val = tr[i].u = tr[i].fa = 0;  
        tr[i].son.clear();  
        arr[i] = read();  
    }  
    for (re int i = 1;i <= n;i++){  
        if (arr[i] == tr[p].u) p = tr[p].fa;  
        else{  
            int v;  
            if (!tr[p].son.count(arr[i])){  
                tr[p].son[arr[i]] = v = ++idx;  
                tr[v] = {-1,arr[i],p};  
            }  
            else v = tr[p].son[arr[i]];  
            p = v;  
        }  
        tr[p].val++;  
        ans += tr[p].val;  
    }  
    printf("%lld\n",ans);  
}  
  
int main(){  
    T = read();  
    while (T--) solve();  
    return 0;  
}