#P12608. 骷髅打金服

骷髅打金服

题目背景

下图是一个经典算法的错误实现。

题目描述

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

求合法的非空子段个数。两个子段不同当且仅当它们在原序列中的出现位置不同。

输入格式

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

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

第一行一个整数 nn

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

输出格式

TT 行,每行一个整数,表示一组数据的答案。

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,1]
  • [1,2][1,2]
  • [1,4][1,4]
  • [2,2][2,2]
  • [2,3][2,3]
  • [2,5][2,5]
  • [3,3][3,3]
  • [3,4][3,4]
  • [4,4][4,4]
  • [4,5][4,5]
  • [5,5][5,5]

数据范围

本题采取子任务依赖,未通过当前子任务依赖的子任务会导致当前子任务得零分。

对于 100%100\% 的数据,T1,1n,n106,1ainT\ge 1,1\le n,\sum n\le 10^6,1\le a_i\le n

子任务 nn\le n\sum n\le 特殊性质 分值 时限 依赖子任务
11 100100 10001000 - 1010 1s
22 80008000 4×1044\times 10^4 11
33 - 2×1052\times 10^5 1ai41\le a_i \le 4 2020
44 aa 的每个元素在 [1,n][1,n] 均匀随机 1010
55 1ai141\le a_i\le 14 2020 33
66 - 1010 151\sim 5
77 5×1055\times 10^5 161\sim 6
88 10610^6 171\sim 7