307798: CF1418G. Three Occurrences
Memory Limit:512 MB
Time Limit:5 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Three Occurrences
题意翻译
# 题目描述 现在我给你一个由 $n$ 个整数组成的数组 $a$ ,我们表示子数组 $a[l\dots r]$ 为数组 $[a_l,a_{l+1}\dots ,a_r](1\le l \le r \le n)$ 。 如果子数组中出现的每个整数恰好出现了三次,我们则称这个子数组为好子数组。例如,数组 $[1,2,2,2,1,1,2,2,2]$ 有三个好子数组: - $a[1..6]=[1,2,2,2,1,1] ;$ - $a[2..4]=[2,2,2] ;$ - $a[7..9] = [2, 2, 2]$. 现在我想让你求这个数组 $a$ 中有多少个好子数组。 # 输入格式 输入的第一行包含一个整数 $n(1\le n\le 5\cdot 10^5)$ 。 第二行行包含 $n$ 个整数 $a_1,a_2 \dots a_n(1\le a_i \le n)$ 。 # 输出格式 打印一个整数,代表数组 $a$ 的好子数组的个数。题目描述
You are given an array $ a $ consisting of $ n $ integers. We denote the subarray $ a[l..r] $ as the array $ [a_l, a_{l + 1}, \dots, a_r] $ ( $ 1 \le l \le r \le n $ ). A subarray is considered good if every integer that occurs in this subarray occurs there exactly thrice. For example, the array $ [1, 2, 2, 2, 1, 1, 2, 2, 2] $ has three good subarrays: - $ a[1..6] = [1, 2, 2, 2, 1, 1] $ ; - $ a[2..4] = [2, 2, 2] $ ; - $ a[7..9] = [2, 2, 2] $ . Calculate the number of good subarrays of the given array $ a $ .输入输出格式
输入格式
The first line contains one integer $ n $ ( $ 1 \le n \le 5 \cdot 10^5 $ ). The second line contains $ n $ integers $ a_1 $ , $ a_2 $ , ..., $ a_n $ ( $ 1 \le a_i \le n $ ).
输出格式
Print one integer — the number of good subarrays of the array $ a $ .
输入输出样例
输入样例 #1
9
1 2 2 2 1 1 2 2 2
输出样例 #1
3
输入样例 #2
10
1 2 3 4 1 2 3 1 2 3
输出样例 #2
0
输入样例 #3
12
1 2 3 4 3 4 2 1 3 4 2 1
输出样例 #3
1