CF459D Pashmak and Parmida's problem
题目描述
Parmida 是一个聪明的女孩,今年她想参加奥林匹克竞赛。当然,她也希望自己的搭档同样聪明。为此,Parmida 给 Pashmak 准备了下面这道测试题。
给定由 n 个整数构成的序列 {a1,a2,…,an}。定义 f(l,r,x) 表示满足 l≦k≦r 且 ak=x 的下标 k 的数量。
请计算有多少对下标 (i,j) 满足 1≦i<j≦n 且 f(1,i,ai)>f(j,n,aj)。
其中,f(1,i,ai) 表示 ai 在 a1,a2,…,ai 中出现的次数,也就是 ai 从左往右数第几次出现;f(j,n,aj) 表示 aj 在 aj,aj+1,…,an 中出现的次数,也就是 aj 从右往左数第几次出现。
输入格式
第一行输入一个整数 n(1≦n≦106) 代表序列中的元素数量。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$ 代表给定的序列。
输出格式
在一行上输出一个整数,代表满足条件的下标对数量。
测试样例
7
1 2 1 1 2 2 1
8
样例 1 解释
序列为 {1,2,1,1,2,2,1}。先计算每个位置对应的两个量:
∙从左往右数,ai 的出现次数 f(1,i,ai) 依次为 1,1,2,3,2,3,4;
∙从右往左数,aj 的出现次数 f(j,7,aj) 依次为 4,3,3,2,2,1,1。
再统计满足 i<j 且前者大于后者的下标对:
∙当 j=5 时,f(5,7,a5)=2,它前面的 f(1,i,ai) 中只有 i=4 的 3 大于 2,贡献 1;
∙当 j=6 时,f(6,7,a6)=1,它前面的 f(1,i,ai) 中 i=3,4,5 的 2,3,2 均大于 1,贡献 3;
∙当 j=7 时,f(7,7,a7)=1,它前面的 f(1,i,ai) 中除 i=1,2 外均大于 1,贡献 4。
其余 j 均无贡献,因此答案为 1+3+4=8。
3
1 1 1
1
样例 2 解释
序列为 {1,1,1},f(1,i,ai) 依次为 1,2,3,f(j,3,aj) 依次为 3,2,1。满足 i<j 且前者大于后者的只有 i=2,j=3 这一对,因为 2>1,所以答案为 1。
5
1 2 3 4 5
0
样例 3 解释
序列中元素两两不同,因此每个位置的这两个量都为 1。任意 i<j 都有 f(1,i,ai)=f(j,5,aj)=1,不满足严格大于关系,所以答案为 0。