ARC116 B Products of Min-Max
寄与分を考える. 与えられた整数列$ Aをソートして考えても答えは変わらない. ここで$ maxの値を$ A_iに固定してみる. すると, $ A_i, A_{i - 1}, A_{i - 2}, A_{i - 3}, A_{i - 4}...が$ minとなる回数はそれぞれ$ 1, 1, 2, 4, 8, ...回となる. 求めたいのは$ maxと$ minの掛け算だが, これはあらかじめ$ A_i + A_{i - 1} + 2A_{i - 2} + 4A_{i - 3} + 8A_{i - 4}, ...を求めておき(これを$ kとおく), それを$ A_iと掛けることによって求められる(分配法則を用いるとこれが正しいことがわかる). $ kは累積和を応用することにより求められる. 計算量は$ O(N)である.