V

解説

愚直に$(i,j,k)$の組み合わせを全列挙した場合、時間計算量が $O(N^3)$ となり、実行時間制限に間に合いません。よって計算量を減らす工夫を考えます。 ここで、次のような問題を考えます。

• $a_i = a_k$ となる 各 $(i,k)$ について、$a_i > a_j$ を満たす $j (i < j < k)$ の個数を求めよ。

この値は、次のようなDPを考えることで求めることができます。

• $dp[i][k] = (Aのi番目の要素からk番目の要素までのうち、a_i未満であるものの個数)$

ここで、各 $dp[i]$ についてDPの値は、累積和を用いることで $O(N)$ で計算できるため、DPテーブル全体を $O(N^2)$ で構築できます。後はDPテーブルのうち、$a_i = a_k$ を満たすような $dp[i][k]$ の総和を求めれば良いです。全体の時間計算量は $O(N^2)$ となり、本制約において実行時間制限に間に合います。よって、この問題を解くことができました。

余談

この問題は 平衡二分木を用いて時間計算量 $O(NlogN)$ で解くこともできます。解説は $O(NlogN)$ 制約で出したときにでも...