数列のスコアは、以下の方法で求めることが出来ます。

• 変数 \(X = N, Y=N,Z=0\) を用意する。
• \(A,B\) をまとめて昇順にソートし、小さい順に見ていく。
• 今見ている数字が \(A\) 由来であれば、 \(Y\) と今見ている数字の積を \(Z\) に加算し、その後 \(X\) を \(1\) 減らす。
• 今見ている数字が \(B\) 由来であれば、 \(X\) と今見ている数字の積を \(Z\) に加算し、その後 \(Y\) を \(1\) 減らす。
• 最終的に得られた \(Z\) の値がスコアに一致する。

\(A_i \leq B_i\) であると仮定して一般性を失いません。操作によって答えがどのように変化するかに着目します。

\(A_i \leq A_j\) を満たす組 \((i,j)\) について、 \(A_i,B_i,A_j,B_j\) の大小関係で場合分けします。

• \(A_i\leq B_i \leq A_j \leq B_j\) のとき：操作は答えに影響しません。
• \(A_i\leq A_j \leq B_i \leq B_j\) のとき：\(i,j\) どちらかにのみ操作をした場合、答えが \(B_i-A_j\) 増加します。
• \(A_i\leq A_j \leq B_j \leq B_i\) のとき：\(i,j\) どちらかにのみ操作をした場合、答えが \(B_j-A_j\) 増加します。

以上の考察により、以下の問題が解ければいいことがわかります。

\(N\) 個の区間 \([A_1,B_1], \dots, [A_N,B_N]\) が与えられる。はじめ \(N\) 個の区間は全て白色である。\(N\) 個の区間のうちいくつかを選び黒色に塗ることが出来る。以下の値を最大化せよ。

• 色が相異なる区間の組全てに対する、その二つの区間の共通部分の長さの総和

区間を隣り合った端点で分解します。それぞれの分解された区間を覆っている区間の個数を \(c\) とすると、以下が答えの上界となります。

• 分解された区間それぞれについての、区間の長さ \(\times \lfloor \frac{c}{2} \rfloor \times \lceil\frac{c}{2} \rceil\) の総和

実はこの上界は達成可能です。

区間の端点 \(2N\) 個を順に並べ、 \(2\) 個ずつに分けます。このとき、ペアは \(N\) 個できますが、それぞれについて以下の制約を課すこととします。

• ペアの点に対応する区間の番号を \(u,v\) とする。 ペアの点の始点、終点の状態が同じとき、 区間 \(u\) と区間 \(v\) は異なる色でなくてはならない。ペアの点の始点、終点の状態が異なる時、区間 \(u\) と区間 \(v\) は同じ色でなくてはならない。

上記の制約全てを満たす区間の塗り方が存在すれば、上界を達成可能なことがわかります。

ここで、常に上記の制約全てを満たす区間の塗り方が存在することが示せます。

実際の構築も、 dfs などを用いることで容易に行えます。計算量はソートがボトルネックとなり \(Ο(N\log N)\) です。

原案：nok0

解答：noimi