C - Partially Sort Editorial
by 
PCTprobability
この問題は、\(P\) の部分列全てに対する、部分列だけをソートしたときの転倒数の総和を求める問題です。転倒数としては、両方部分列に選ばれなかったペア、片方が部分列に選ばれたペア、両方部分列に選ばれたペアの \(3\) 種類の寄与があります。
\(1\) 種類目の寄与はもとから転倒しているペアの個数 \(I\) にほかの \(N-2\) 要素を部分列に選ぶかを掛け合わせて \(2^{N-2}I\) となります。そして、\(3\) 種類目の寄与はソートされた部分列で転倒ペアは発生しえないので \(0\) です。
問題は \(2\) 種類目です。\(P_i\) を選ばなかったとして、部分列に選んだほかの要素との転倒数について考えます。まず、\(P\) の値を以下の \(4\) 種類に分別します。
- \(j < i,P_j < P_i\) を満たす \(j\)
- \(j < i,P_j > P_i\) を満たす \(j\)
- \(i < j,P_i < P_j\) を満たす \(j\)
- \(i < j,P_i > P_j\) を満たす \(j\)
それぞれ \(A,B,C,D\) 個あるとして、そのうち部分列には \(a,b,c,d\) 個選ばれたとしましょう。このとき、\(P_i\) と部分列に選ばれた要素の転倒数は \(B+D-2\min(b,d)\) となります。つまり、\(\sum_{b=0}^{B} \sum_{d=0}^{D} \binom{B}{b} \binom{D}{d} \min(b,d)\) を求めればよいです。
\(\min\) が扱いづらいので \(b \le d\) という条件を付け加えます。すると、\(\sum_{b=0}^{B} \sum_{d=b}^{D} \binom{B}{b} \binom{D}{d} b\) を求めることとなります。そして、この式は以下のように解釈できます。
- \(B\) 個の互いに区別できる赤いボールと \(D\) 個の互いに区別できる青いボールがある。これらからいくつかのボールを選ぶが、選んだ赤いボールの個数は選んだ青いボールの個数以下でなければならない。そのような選び方全てに対する選んだ赤いボールの個数の総和を求めよ。
赤いボール \(1\) 個あたりの寄与を考えると、以下の問題に帰着されます。
- \(B-1\) 個の互いに区別できる赤いボールと \(D\) 個の互いに区別できる青いボールがある。これらからいくつかのボールを選ぶが、選んだ赤いボールの個数は選んだ青いボールの個数 \(-1\) 以下でなければならない。そのような選び方の個数を求めよ。
青いボールについて選ぶかどうかを反転させることで、「選んだ赤いボールの個数が選んだ青いボールの個数 \(-1\) 以下な選び方」と「赤いボールと青いボールを合計 \(D-1\) 個以下選ぶ選び方」は一対一対応します。つまり、\(\sum_{i=0}^{D-1} \binom{B+D-1}{i}\) が求まればよいです。
\(b > d\) の場合も同じように計算することが出来ます。よって、適切な prefix sum を \(2N\) 回計算出来ればよいですが、これは有名問題で Mo’s algorithm などを用いて \(\mathrm{O}(N \sqrt N)\) で計算できます。よって、この問題は \(\mathrm{O}(N \sqrt N)\) で解くことが出来ました。