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;
}