PAST3N
考えたこと
範囲をソートするクエリを素朴に実装するとO(NlogN)
明らかに間に合わない
O(logN)ぐらいにならないといけない
どうやって？
ソート済みのところからスワップを高々Q回行うので、ソート前の列はかなりソート済みに近い
ソート済みの列を一つの塊として扱おう
[x, y)をタプル
(x, y) で表現？zでのスワップは [x, y) → [x, z), [z+1, z+2), [z, z+1), [z+2, y)
区間はオーバーラップしないので先頭だけ見てソートすれば良い
その後、連続するならくっつける？
ソートの計算量が、それまでにスワップした回数Mを使ってO(MlogM)になる
これを増やすのにQを消費するからあまり重たくできない
ソートをX回やるならMは平均してQ/Xなのでソートクエリ全体の計算量はO(X Q/X log(Q/X)) = O(Q log(Q/X))
クエリ全体の平均計算量がO(logN)以下になる
間に合うだろう
これをどう実装するのか
スワップでオブジェクトの挿入が起きるので配列はダメ
でもzで分割するってなった時に、分割対象のオブジェクトをすぐに見つけたい
二分探索するなら配列でないといけない
リンクトリストにすると探索が線形オーダーになってしまう
なんかこういう「配列でもリンクトリストでもダメ」ってケース、フェニック木なことが多い
フェニック木で1を立てることで集合を表現したものは配列同様に対数オーダーで二分探索できるが、挿入削除が定数オーダーである
ただしこれは順序を持たないので別途リンクトリストで順序を持たせたい
二分探索で見つけた後、リンクトリストの該当ノードを定数オーダーで見つけたい
これはスカスカのリンクトリストで実現できる
サイズNの配列を先に確保してしまって、ほとんど空で使う
というわけでこれでいける
実装
ソートはどうやるんだ？
あ、前回の図ではダメだ
これはフェニック木に「断片のstartの値」が入ってるが、実際のソートやスワップのクエリは「配列上の位置」に対して掛かる
それが検索できないといけない
むしろ前後の値はフェニック木の二分探索で手に入るからリンクトリストが要らないのでは
startとendの差から「次の断片」がどこにあるかは定数オーダーでわかる
フェニック木の実装が1-originなのが混乱を招いたのでインターフェースを0-originにした
場合わけが大変で混乱してきた
一旦中断
ネットで解説を探すともっとシンプルにやってそうな感じ
スワップされたところを記録しておいて、ソートの時にはそこだけを確認すれば良い
ほんとにそうなのかいまいち自信が持てないけどその方針で実装してみよう
サンプルは通ったがジャッジは11TLE
一度立てたフラグを消してない
消すとサンプルが通らなくなる
バグってるのにフラグを消してなかったことでたまたま通ってただけ
スワップの結果、手前に転倒が発生することがある
スワップの際(ソートの時に行われるものも含め)転倒しうるところにフラグを立てる
ソートはフラグを消しながら行う
これでACした
AC:
pythondef solve(N, Q, QS):
values = list(range(1, N + 1))
ft = FenwickTree(N)
def swap(i):
values[i], values[i + 1] = values[i + 1], values[i]
if i > 0:
ft.set(i - 1, 1)
ft.set(i, 1)
if i < N - 1:
ft.set(i + 1, 1)
for t, x, y in QS:
if t == 1:
x -= 1
# swap query
swap(x)
else:
x -= 1
y -= 1
# sort query
s = ft.sum(x) + 1
pos = ft.bisect(s) - 1
while pos < y:
ft.set(pos, 0)
while pos >= x and values[pos] > values[pos + 1]:
swap(pos)
pos -= 1
pos = ft.bisect(s) - 1
return valuesRelated Pages
- →abc168×第三回 アルゴリズム実技検定×abc169×abc173×僕のatcoderの学び方(〜緑)×arc106×僕のatcoderの学び方(〜水色)×abc183×abc187×僕のatcoderの学び方(〜青)→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]