#CF459D. Pashmak 和 Parmida 的问题

Pashmak 和 Parmida 的问题

CF459D Pashmak and Parmida's problem

题目描述

\hspace{15pt}Parmida 是一个聪明的女孩,今年她想参加奥林匹克竞赛。当然,她也希望自己的搭档同样聪明。为此,Parmida 给 Pashmak 准备了下面这道测试题。

\hspace{15pt}给定由 nn 个整数构成的序列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\}。定义 f(l,r,x)f(l,r,x) 表示满足 l≦k≦rl \leqq k \leqq r 且 ak=xa_k=x 的下标 kk 的数量。

\hspace{15pt}请计算有多少对下标 (i,j)(i,j) 满足 1≦i<j≦n1 \leqq i<j \leqq n 且 f(1,i,ai)>f(j,n,aj)f(1,i,a_i)>f(j,n,a_j)。

\hspace{15pt}其中,f(1,i,ai)f(1,i,a_i) 表示 aia_i 在 a1,a2,…,aia_1, a_2, \dots, a_i 中出现的次数,也就是 aia_i 从左往右数第几次出现;f(j,n,aj)f(j,n,a_j) 表示 aja_j 在 aj,aj+1,…,ana_j, a_{j+1}, \dots, a_n 中出现的次数,也就是 aja_j 从右往左数第几次出现。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦106)n \left(1 \leqq n \leqq 10^6\right) 代表序列中的元素数量。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$ 代表给定的序列。

输出格式

\hspace{15pt}在一行上输出一个整数,代表满足条件的下标对数量。

测试样例

7
1 2 1 1 2 2 1
8

样例 1 解释

\hspace{15pt}序列为 {1,2,1,1,2,2,1}\{1, 2, 1, 1, 2, 2, 1\}。先计算每个位置对应的两个量:

∙ \hspace{23pt}\bullet\,从左往右数,aia_i 的出现次数 f(1,i,ai)f(1,i,a_i) 依次为 1,1,2,3,2,3,41,1,2,3,2,3,4;

∙ \hspace{23pt}\bullet\,从右往左数,aja_j 的出现次数 f(j,7,aj)f(j,7,a_j) 依次为 4,3,3,2,2,1,14,3,3,2,2,1,1。

\hspace{15pt}再统计满足 i<ji<j 且前者大于后者的下标对:

∙ \hspace{23pt}\bullet\,当 j=5j=5 时,f(5,7,a5)=2f(5,7,a_5)=2,它前面的 f(1,i,ai)f(1,i,a_i) 中只有 i=4i=4 的 33 大于 22,贡献 11;

∙ \hspace{23pt}\bullet\,当 j=6j=6 时,f(6,7,a6)=1f(6,7,a_6)=1,它前面的 f(1,i,ai)f(1,i,a_i) 中 i=3,4,5i=3,4,5 的 2,3,22,3,2 均大于 11,贡献 33;

∙ \hspace{23pt}\bullet\,当 j=7j=7 时,f(7,7,a7)=1f(7,7,a_7)=1,它前面的 f(1,i,ai)f(1,i,a_i) 中除 i=1,2i=1,2 外均大于 11,贡献 44。

\hspace{15pt}其余 jj 均无贡献,因此答案为 1+3+4=81+3+4=8。

3
1 1 1
1

样例 2 解释

\hspace{15pt}序列为 {1,1,1}\{1,1,1\},f(1,i,ai)f(1,i,a_i) 依次为 1,2,31,2,3,f(j,3,aj)f(j,3,a_j) 依次为 3,2,13,2,1。满足 i<ji<j 且前者大于后者的只有 i=2,j=3i=2,j=3 这一对,因为 2>12>1,所以答案为 11。

5
1 2 3 4 5
0

样例 3 解释

\hspace{15pt}序列中元素两两不同,因此每个位置的这两个量都为 11。任意 i<ji<j 都有 f(1,i,ai)=f(j,5,aj)=1f(1,i,a_i)=f(j,5,a_j)=1,不满足严格大于关系,所以答案为 00。