No.121

最初に $A_i$ を座標圧縮しておく.

3つ組の真ん中の要素 $j$ を固定したときの門松列を数え上げ, $j$ を $1 \dots N-1$ まで動かす.

真ん中の要素を固定したときの左右の高さが同じでも構わないとした場合の門松列の数を数える.

これは左右がともに $A_j$ より大きいか, ともに $A_j$ より大きい組み合わせの数となる.

$A_i < A_j$ となる $A_i$ の数を $P_j$, $A_k < A_j$ となる $A_i$ の数を $Q_j$ とすると, 左右がともに $A_j$ より小さい組み合わせの数は $P_jQ_j$ となる. ともに大きい場合も同様に計算する.

$P_j, Q_j$ は Binary Indexed Tree を使えば $j$ を動かしても高速に計算できる.

ここから左右の高さが同じ組み合わせの数 $R_j$ を引く. $R_j$ は $j$ を動かしたときに差分更新できる.

このままだと3つとも同じ高さになる組み合わせを引きすぎているので, 最後にこれを追加する.