ferinの競プロ帳

競プロについてのメモ

codeforces #261 div2 D. Pashmak and Parmida's problem

問題ページ
Problem - D - Codeforces

概要

数列aが与えられる。f(l,r,x) を l<=k<=r の範囲で a[k] = xとなる要素の個数と定義する。f(1,i,a[i]) < f(j,n,a[j])となる(i, j)の組(1 <= i < j <= n)の個数を求めろ。

解法

まず、f(1, i, a[i])を計算する。それぞれの要素の個数を数える配列を用意して順に計算していけばよいが、a[i]<=10^9より普通にもつことはできない。そこで座圧しておく。f(j, n, a[j])も同様に事前に計算しておき、b[i] = f(1,i,a[i])、c[i] = f(i,n,a[i])と配列でもっておく。
b[i]>c[j]となるような(i,j)の組の個数を求めればいい。BITを用いて今までに出てきた要素別の個数を数えておくとO(nlogn)でこの処理はできる。