Codeforces Round #560 (Div. 3) E. Two Arrays and Sum of Functions

長さ $n$ の数列 $a, b$ が与えられます. この数列に対して, 関数 $f$ を以下のように定めます:

$f(l, r) = \sum_{l \le i \le r} a_i \times b_i$

$b$ の要素を自由に並び変えられるとき, $\sum_{1 \le l \le r \le n} f(l, r)$ の最小値を求めてください. ただし答えが非常に大きくなる可能性があるので, $998244353$ で割った余りを求めてください.

$i$ 番目の要素の計算にほかの要素がかかわってこないので, 主客逆転することで求められそうです. つまり, $i$ 番目の要素は何回答えに足されるか？を考えようということです.

そのためには $i$ 番目の要素を含むような区間の選び方は何通りあるかを求める必要があります. もし, $i$ 番目の要素を含むような区間の選び方が $k_i$ 通りなら,

$\sum_{1 \le l \le r \le n}\sum_{l \le i \le r} a_i \times b_i = \sum_{1 \le i \le n}k_ia_i\times b_i$

のように式変形をすることができるので, うまいこと $b$ を求めれば線形で答えが出ます.

まず, $k_i$ についてですが, これは $i$ 番目の要素が選ばれるには $i$ 以下から $l$ が, $i$ 以上から $r$ が選ばれればよいです. これは $i\times (n-i+1)$ 通りだけあります.

さらに $b$ の並び替えは, $k_ia_i$ の大きいものに $b_i$ が小さいやつを割り当てていけばいいです. このようなマッチングが最小になる事実は有名で, 例えばこれなどでみることができます(ネタバレ注意).