题目内容

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

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

树状数组

前置知识树状数组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$