E: Young Maids - AtCoder Regular Contest 080
N個の順列pが与えられる。この順列pの任意の隣り合った2個の要素を取り除き、別の順列qの先頭に追加する、という操作を繰り返しpがからになるまで行う。最初qが空であるとする時、辞書順最小のqを構成せよ。
実験すると、pの先頭及び2番目に来る要素はpの偶数番目(0-indexedとする)の最小値(a[i]とする)、及びその最小値のある場所よりも右にある奇数番目の最小値(a[j]とする)である。これらを取り除いた後、次に来るのは一つ前の操作によって取り除かれたi番目及びj番目を除く [0, i), [i + 1, j), [j + 1, N) の範囲について、それぞれ同じ操作を行い辞書順最小となるものである。この3個のうち、どれが選ばれるかは、それぞれの範囲に置いて偶数番目の要素が最小になる範囲で決定される。
そこで、まず「投入された範囲の偶数番目の最小値」が最も小さい物が先頭に来るような、優先度付きキューを用意し、[0, N) の範囲を入れる。このキューについて、先頭を取り出し奇数番目最小の位置も計算し操作を行う。操作を行った後、分割された3個の範囲について、空でなければ、キューに再投入する、という操作を行う。
さて、「投入された範囲の偶数番目の最小値」であるが、あらかじめ順列のSegment treeを偶数番目は元の順列、奇数番目はINFを入れておくと、求めることができる。しかし、キューに投入された範囲によっては先頭が元々の奇数番目ということもあり得るため、偶数番目はINF、奇数番目は元の順列という2種類作っておき、範囲の最初の要素が元の順列で奇数番目であったか偶数番目であったかによってどちらのSegment treeを使うかを決定する。
ちなみにこのキューのComparatorを素直に書くと優先度付きキューの計算回数がO(logN), Segment treeの最小値計算がO(log N)かかるので、結局O(logN^2)かかってしまう。そこで、キューへの投入時に{left, right, min} と言うかたちで最小値をあらかじめ計算してしまい、3番目の要素でComparatorを書くとO(log N)にすることが可能。
全体ではO(N logN)だと思うのだが、分割の仕方をよくシミュレートしていないのであまり自信はない。
