ありえる集合のうち、写っている星の集合の中で最も暗い星が \(i\) 番目の星であるような集合は \(\bigl(j\lt i\) かつ \(B _ j\lt B _ i\) なる \(j\) の個数\({}+1\bigr)\times\bigl(j\gt i\) かつ \(B _ j\lt B _ i\) なる \(j\) の個数\({}+1\bigr)\) 通りあります。

すべての \(i\) について、\(j\lt i\) かつ \(B _ j\lt B _ i\) なる \(j\) の個数や \(j\lt i\) かつ \(B _ j\lt B _ i\) なる \(j\) の個数を求めることは、転倒数を \(O(N\log N)\) 時間で求めるアルゴリズムを少し変形することで同様に \(O(N\log N)\) 時間でできます。 例えば、\(B _ i\) の昇順になるような順序で処理を行い、セグメント木やフェニック木を用いてこれまで処理を行った \(i\) のうち現在の \(i\) より大きいものと小さいものがそれぞれいくつかあるか求めるようなアルゴリズムで実現されます。

このようにして得られた情報をもとに \(O(N)\) 時間で答えを求めることができるため、全体の計算時間は \(O(N\log N)\) 時間となり、十分高速です。

\((B _ i)\) が \((1,2,\ldots,N)\) の並べ替えであることから、少し実装を単純にできる場合もあります。

実装例は以下のようになります。

#include <iostream>
#include <ranges>
#include <atcoder/fenwicktree>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;
    atcoder::fenwick_tree<unsigned> bit(N);
    unsigned long ans{};
    for (const auto B : views::istream<unsigned>(cin)) {
        const unsigned long left{bit.sum(0, B)}, right{B - 1 - left};
        ans += (left + 1) * (right + 1); // (左側の明るい星の個数 + 1) × (右側の明るい星の個数 + 1)
        bit.add(B - 1, 1); // BIT を更新
    }
    cout << ans << endl;
    return 0;
}