AtCoder Grand Contest 005: B. Minimum Sum

http://agc005.contest.atcoder.jp/tasks/agc005_b

解法

最小値が v になるような区間の個数を数える問題を考えてみよう。

たとえば a=[1,5,8,3,9,6,7,2,4]、最小値が 3 になる区間の数を数えるなら次のようなグラフを作る。

f:id:pekempey:20161002041415p:plain

3 を通るようなパスの個数を数えれば良くて、これは [5,8,3] と [3,9,6,7] からそれぞれ一つずつ取ってペアにするパターン数と一致するので 3×4=12 通りだと分かる。

3より左(右)にいくつ連結している頂点があるかは union find のノードに連結成分のサイズを持たせておけば計算できる。

cheflong でもっと難しいのがある。https://www.codechef.com/AUG16/problems/GOODPROB