ABC209-F Deforestation O(N log^2 N)解

atcoder.jp
が $O(N \log^2 N)$ で解けるよという話です。特に何か面白いと言ったことはなくて、ただの土木ですが、一応。

必要十分条件は
各 $i=1,2,\dots,N-1$ について
・ $H_i < H_{i+1}$ なら $P_i > P_{i+1}$
・ $H_i > H_{i+1}$ なら $P_i < P_{i+1}$
となっていることです。

ここで、 $H_i = H_{i+1}$ であるような $i$ について $i,i+1$ で区切って、それぞれの列について問題を解いてからその積に適切な多項係数をかければよいことを考えると、結局各 $i$ について $P_i > P_{i+1}$ または $P_i < P_{i+1}$ という条件が設定されていて、その条件を満たすような順列を数え上げれば良いです。これはEDPC-Tなわけですが、これは包除原理を考えると、分割統治+FFTで $O(N \log^2 N)$ で解くことができます。
詳しくは、Nachiaさんの裏EDPCなどを参照してください :

www.mathenachia.blog

実装例だけ載せておきます:

atcoder.jp