树状数组

前置知识树状数组https://oi-wiki.org/ds/fenwick/ $\\$ 对于目前的$i$只需要利用$map$映射$f(1,i,ai)$的值就可以知道也就是$mp[a[i]]$，怎么快速知道有多少个$f(j,n,aj)$小于$mp[a[i]]$,用一个树状数组维护，就可以直接区间查找了.$\\$ 具体做法 $add(f(j,n,aj),1),1<=j<=n$$\\$ 枚举$i$然后$add(f(i,n,ai),-1)$$ans+=query(1,f(i,n,ai)-1)$$\\$ 整体时间复杂度$o(nlog_2n)$ $\\$

代码如下

$cpp$

题目内容

小明有一个长度为$n$的数组$a$，记$f(l,r,x)$为区间[$l,r$]内$x$的出现次数。

现在小明想知道有多少对$i<j$满足$f(1,i,a_i)>f(j,n,a_j)$。

输入描述

第一行输入一个整数 $n$

第二行$n$个整数$a_1,a_2,...,a_n$。

$1≤n≤10^5$

$1≤a_i≤10^9$

输出描述

输出一个整数表示答案。

样例1

输入

6
1 2 1 2 2 1

输出

5

说明

存在以下五对($i,j$)满足条件：$(3,5)(3,6)(4,5)(4,6)(5,6)$

样例2

输入

输出