题目背景
下图是一个经典算法的错误实现。
题目描述
长为 n 的序列 a 的一个非空连续子段是合法的,当且仅当其中所有出现过的元素出现次数全相等。
求合法的非空子段个数。两个子段不同当且仅当它们在原序列中的出现位置不同。
输入格式
第一行一个整数 T,表示数据组数。
接下来 T 组数据,每组数据格式如下:
第一行一个整数 n。
接下来一行 n 个整数,描述序列 a。
输出格式
T 行,每行一个整数,表示一组数据的答案。
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
25
8
11
26
34
提示
样例解释 #1
对于第三组数据,合法的连续非空子序列如下:
- [1,1]
- [1,2]
- [1,4]
- [2,2]
- [2,3]
- [2,5]
- [3,3]
- [3,4]
- [4,4]
- [4,5]
- [5,5]
数据范围
本题采取子任务依赖,未通过当前子任务依赖的子任务会导致当前子任务得零分。
对于 100% 的数据,T≥1,1≤n,∑n≤106,1≤ai≤n。
子任务 |
n≤ |
∑n≤ |
特殊性质 |
分值 |
时限 |
依赖子任务 |
1 |
100 |
1000 |
- |
10 |
1s |
|
2 |
8000 |
4×104 |
1 |
3 |
- |
2×105 |
1≤ai≤4 |
20 |
|
4 |
a 的每个元素在 [1,n] 均匀随机 |
10 |
5 |
1≤ai≤14 |
20 |
3 |
6 |
- |
10 |
1∼5 |
7 |
5×105 |
1∼6 |
8 |
106 |
1∼7 |