CSAcademy 10 D. Subarray Medians - 1日9時間寝たい

問題

https://csacademy.com/contest/round-10/task/subarray-medians/

問題概要

与えられた数列に対して、全ての連続した部分列（奇数長）を考えl×r×([l, r]のmedian)の総和を求める。

方針

medianを更新しながら、l=1..N, r=l..Nとして部分列を全通り考えます。

要素がちょっとずつ増えたり、減ったりしたくらいでmedianは大きく変わらないだろうという気持ちを持ちます。すると、部分列に含まれる各要素に対して、自分の次に大きい要素・自分の次に小さい要素を覚えておけばよさそうです。つまり、部分列をソートしたときの各要素について、自分の右隣・左隣の要素を覚えておきます。

要素を追加するときの操作を考えるとmedianから順に辿っていくことになって、これは最悪(今の部分列の長さ/2)回くらい辿らなければいけません。そこで、要素を削除するほうを考えます。いま、削除したい要素の両隣の要素はわかっているので、削除したい要素をxとすると

xの右の左=xの左
xの左の右=xの右

と更新すれば良いと分かります（図を見て察してください）。

f:id:poyopoyoyon:20170806155626p:plain

部分列の長さが偶数のときは２つのmedianの候補のうち、小さいほうをmedianとします*1。つまり、1 2 3 4のmedianを2ということにします。要素を削除したあとmedianを更新するかどうかは、削除した要素とmedianとの大小・部分列の長さの偶奇によって適当に場合分けします。たとえば、長さ5でmedianが3の数列 1 2 3 4 5 から要素を削除すると