AGC005 B Minimum Sum - 足跡-sokuseki-

昨日解いていて、解説を見ても理解するのに手こずったので、考え方を書いてみる(一応この問題について書いてるブログはあったけど、解法が違ったので、自分用に)。

B: Minimum Sum - AtCoder Grand Contest 005 | AtCoder

問題概要

$1$ から $N$ までの数字を並べ替えた長さ $N$ の数列 $a_1, a_2, … , a_N$ が与えられるので
$\sum_{l=1}^{N} \sum_{r=l}^{N} min(a_{l}, a_{l+1}, … , a_{r})$ を求める。

つまり、長さ $N$ の数列の $_N C _2$ 個の区間それぞれについて最小値を求め、それの合計を求める。

制約は $N <= 2 \times 10^5$ のため、計算量は高々 $O(N)$ か $O(N log N)$ 。

TLE解法

自力で思いついたのは全区間の最小値を順番に足していく $O(N^2)$ の解法。
調べる区間の幅をだんだん大きくしていくという考え方。

Submission #1101992 - AtCoder Grand Contest 005 | AtCoder

ansの初期値に代入している $\frac{n(n+1)}{2}$ は、隣り合う1項の最小値(つまりその項自身)の合計値。数列には $1$ から $N$ までの数がそれぞれ1回ずつ出てきているので、等差数列の和と考えて計算する。

repの中では、隣り合う $N-i+1$ 項の最小値を計算してansに足していく。

区間(部分数列)でいうと
{ $a_0, a_1$ } { $a_1 , a_2$ } … { $a_{N-2} , a_{N-1}$ }
{ $a_0 , a_1 , a_ 2$ } { $a_1 , a_2 , a_3$ } … { $a_{N-3} , a_{N-2} , a_{N-1}$ }
…
{ $a_0 , … , a_{N-2}$ } { $a_1 , … , a_{N-1}$ }
{ $a_0 , … , a_{N-1}$ }
の最小値を順番に求めている。

setを使った解法

$O(N log N)$ の解法は「最小値が $a_i$ となる区間がいくつあるかを計算し、その区間数と $a_i$ の積の合計を求める」。

$a_i$ が最小値となる区間は、数列の $a_i$ より前の部分で $a_i$ に一番近いところにある $a_i$ よりも小さな値との距離、数列の $a_i$ より後ろの部分で $a_i$ に一番近いところにある $a_i$ よりも小さな値との距離がわかれば求めることができる。

たとえば、{5, 4, 9, 2, 1, 8, 6, 7, 3}という数列の6が最小値となる区間を考える。
6が最小値になる区間は6より小さな値が存在しないので、もとの数列の6より小さい値にだけ色をつけると
{5, 4, 9, 2, 1, 8, 6, 7, 3}
となり、6より小さな値(赤色の数字)が存在しないような区間(部分数列)は{8,6}{8,6,7}{6}{6,7}の4つとなる。
ここで、6が最小値となる区間の左端は、はじめの数列の「6より左にあって6より小さな一番6に近い値(=1)」よりも右で、6よりも右ではない数字になっていることがわかるので、6が最小値となる区間の左端は8,6のどちらかであり、この8,6という左端の候補の数(=2)は「6より左にあって6より小さな一番6に近い値(=1)」と6との距離である。
同様に、6が最小値となる区間の右端は6,7のどちらかであり、右端の候補の数(=2)は「6より右にあって一番6に近い6より小さな値(=3)」と6との距離である。
そして、6が最小値となる区間の数は(左端の候補の数)*(右端の候補の数)より2*2=4個と求めることができる。

今見ている数字 $a_i$ が最小値となる区間の数を求めるためには、 $a_i$ の左右それぞれで、 $a_i$ より小さく $a_i$ に一番近い数との距離が必要になる。よって、要素を自動的にsortしてくれるsetに、 $a_i$ より小さな値の添字を入れておき、 $a_i$ の添字iに一番近い数をlower_boundを使って高速に調べればよい。

$a_i$ が最小値となる区間を調べる際に必要な情報は「 $a_i$ よりも小さな値がどこにあるのか」なので、できるだけ小さな $a_i$ 、つまり1から順番に調べていくと、区間数を調べた後にsetに $a_i$ をそのまま入れることができるので、効率よく求めることができる。

setの要素の挿入に $O(logN)$ 、set内のlower_boundに $O(logN)$ かかるので、 $a_i$ それぞれに対して行っても $O(N log N )$ 。