#P16122. [2026年山东集训一轮]区间很爽

[2026年山东集训一轮]区间很爽

题目描述

定义长为 nn 的序列 aa 的一个非空连续子段是合法的,当且仅当其中所有出现过的元素出现次数全相等。

求合法的非空子段个数。

两个子段不同当且仅当它们在原序列中的出现位置不同。

输入格式

第一行一个整数 TT,表示数据组数。

接下来 TT 组数据,每组数据格式如下:

第一行一个整数 nn。

接下来一行 nn 个整数,描述序列 aa。

输出格式

输出 TT 行,每行一个整数,表示答案。

样例 1 输入

5
9
1 1 1 2 2 2 3 3 3
4
1 1 2 2
5
1 1 2 2 1
10
1 2 2 1 1 2 3 2 3 3
12
1 1 2 3 3 2 1 2 3 3 2 1

样例 1 输出

25
8
11
26
34

数据范围与约定

测试数据满足:

$$T\ge 1,\qquad 1\le n,\qquad \sum n\le 10^6,\qquad 1\le a_i\le n.$$
子任务编号 nn / ∑n\sum n 特殊性质 分值
1 n≤100, ∑n≤1000n\le 100,\ \sum n\le 1000 无 8
2 n≤8000, ∑n≤4×104n\le 8000,\ \sum n\le 4\times 10^4
3 ∑n≤2×105\sum n\le 2\times 10^5 1≤ai≤41\le a_i\le 4 16
4 aa 序列每个元素在 [1,n][1,n] 均匀随机 12
5 1≤ai≤141\le a_i\le 14 20
6 无 12
7 ∑n≤5×105\sum n\le 5\times 10^5
8 ∑n≤106\sum n\le 10^6