この問題は積の和典型と呼ばれる考え方と、大変な場合分けの練習問題です。

積の和典型に関するより易しい類題としては、ABC277-G や ARC157-C 等もあるので、そちらを適宜参照して下さい。

大変な場合分けは、適宜対称性を考えて場合分けを減らし、考慮漏れによるミスが極力起きないようにすることが重要です。

---

[1] 問題の言いかえ

積の和典型を用いると、この問題は以下の問題に言い換えられます。

\(1\leq l_1 < r_1 \leq N\) 、 \(1\leq l_2 < r_2 \leq N\) を満たすような整数組 \((l_1,r_1,l_2,r_2)\) 全てに対して、\(P_{l_1}>P_{r_1},P_{l_2}>P_{r_2}\) をともに満たすような順列の個数を数え、その総和を求めよ。

以下、言いかえ後の問題について考えます。また、\(A\) に含まれる \(-1\) の個数を \(q\) とします。

---

[2] ペアの構造に着目して場合分け

\(1\leq l<r\leq N\) を満たす整数組 \((l,r)\) は以下の \(3\) パターンのいずれかに分類できます。

• 既に \(P_l,P_r\) の値が定まっている。この組をタイプ \(A\) と呼ぶ。
• \(P_l,P_r\) の片方の値が定まっている。この組をタイプ \(B\) と呼ぶ。
• \(P_l,P_r\) の値がともに未定である。この組をタイプ \(C\) と呼ぶ。

\((l_1,r_1,l_2,r_2)\) について、\((l_1,r_1)\) と \((l_2,r_2)\) のタイプに応じて場合分けをしましょう。対称性を考えると以下の \(6\) 通りを考えればよく（\((l_1,r_1)\) と \((l_2,r_2)\) のタイプが異なるとき最後に \(2\) 倍が必要なことに注意してください)、そのうち何個かは自明です。簡単なパターンから順に考えます。

---

以下で用いる記法の整理

• タイプ \(A\) の組 \((l,r)\) であって、 \(P_l > P_r\) を満たすものを良いタイプ \(A\) と呼ぶ。更に、良いタイプ \(A\) の個数を \(a\) と置く。

• タイプ \(C\) の組の個数を \(c\) と置く。

---

• タイプ \(A\) とタイプ \(A\)

求める寄与は \(a^2 \times q!\) です。

• タイプ \(A\) とタイプ \(B\)

タイプ \(B\) の組全てについて条件を満たす順列の個数を数え、その総和に \(a\) を掛ければよいです。

• タイプ \(A\) とタイプ \(C\)

考えられる順列の個数 \(q!\) のうち、あるタイプ \(C\) の組が正しく転倒しているものは対称性より \(q!/2\) です。

求める寄与は \(a\times c \times q!/2 = ac/2\times q!\) です。

• タイプ \(C\) とタイプ \(C\)

\((l_1,r_1,l_2,r_2)\) に含まれる整数の種類数で更に場合分けをします。

a. \(2\) 種類の場合

\((l_1,r_1) = (l_2,r_2)\) です。ゆえに求める寄与は \(c\times q! / 2\) です。

b. \(3\) 種類の場合

\(l_1 = l_2\) を満たす場合、\(r_1<r_2\) と仮定してよいです。

\(l_1\) の位置と取る値を定めると、簡単に寄与が計算できます。

\(l_1\neq l_2\) の場合、\(l_1 < l_2\) と仮定してよいです。 \(l_2=r_1\) の場合と \(r_1 = r_2\) の場合の \(2\) パターンを考えればよいです。

前者は \(l_2\) の位置と取る値を定めると、簡単に寄与が計算できます。

後者は \(r_2\) の位置と取る値を定めると、簡単に寄与が計算できます。

c. \(4\) 種類の場合

\(l_1 < l_2\) という仮定を置き、最後に \(2\) 倍します。含まれる整数を \(x,y,z,w\ (x<y<z<w)\) と置くと、あり得るのは \((l_1,r_1) = (x,y),(x,z),(x,w)\) の \(3\) 通りです。

対称性より条件を満たす順列の個数は全体の \(1/4\) 倍であることに注意すれば、求める寄与は \(2\times \binom{q}{4} \times 3 \times q! / 4 = 3/2\binom{q}{4} \times q!\) です。

• タイプ \(B\) とタイプ \(C\)

タイプ \(B\) の組に含まれる定まった値を全て試します。タイプ \(C\) の組に含まれる整数がタイプ \(B\) の組とどれも異なる場合、独立に考えられるので単に \(1/2\) 倍すればよいです。

そうでない場合は独立でないので、注意して数える必要があります。タイプ \(B\) の未定な値を全て試すことにすれば、寄与の計算がやや易しくなります。

• タイプ \(B\) とタイプ \(B\)

それぞれの組をどれにするかを全探索していると \(O(N^4)\) かかってしまいます。二つの組に含まれる、値が定まっている要素が同じ要素かで場合分けをします。

a.二つの組に含まれる値が定まっている要素が同じ場合

\(3\) パターンの制約について考えればよく、値が定まっている要素を固定することで簡単に計算できます。

b.二つの組に含まれる値が定まっている要素が異なる場合

値が未定の要素が同じ要素かどうかで更に場合分けが生じます。基本的には a と同様に可能ですが、一部の場合は重複して数えないよう適切に取り除く必要があります。

上の \(6\) パターンの場合分けは、全て丁寧に実装することで \(\mathrm{O}(N^2)\) で動作します。よってこの問題は \(\mathrm{O}(N^2)\) で解けます。