数列上の数の組み合わせであって不等式を満たすものの数を数える

まず数列 $a$ の転倒数を求める問題を考えます

より正確には $i < j$ を満たす組 $(i, j)$ であって $a_i > a_j$ となるようなものの数を求める問題で，これは fenwick tree などのデータ構造を使って以下のように解けます

fenwick_tree<long long> ft(MAX);
long long ans = 0;
rep(i, n) {
        ans += ft.sum(a[i] + 1, MAX);
        ft.add(a[i], 1);
}

まず今見ている値を不等式の右辺の値として計算結果に加算して，次に今後その値が不等式の左辺としてどれくらい結果に寄与するかというのを考えているだけです

ところで上記を踏まえると，一般に次のような問題が同様に解けます

$i < j$ を満たす組 $(i, j)$ であってなんらかの制約 $f, g$ について $f(i) > g(j)$ *1 を満たすようなものの数を求めよ
（例題: https://codeforces.com/contest/1324/problem/D）

fenwick_tree<long long> ft(MAX);
long long ans = 0;
rep(i, n) {
        ans += ft.sum(g(i) + 1, MAX);
        ft.add(f(i), 1);
}

(ただし必要に応じて $f, g$ のとりうる値を列挙しておいて自然数に座圧する）

また，より一般に $idx_0 < idx_1 < ... < idx_k$ を満たす $idx$ であって $i = 0, 1, ..., k - 1$ に対するなんらかの $f, g$ を用いた制約 $f_i(idx_i) > g_i(idx_{i + 1})$ を満たすようなものの数を求めることもできて，これは fenwick tree を $k$ 本用意して，各制約ごとに上記とほとんど同様のことをやれば良いです

*1:不等式の向きは $>$ としていますが， $f, g$ を適当に定めればそのようにできるからそう書いているだけであって大小関係について言及しているわけではありません