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の配列を先に確保してしまって、ほとんど空で使う
- というわけでこれでいける
- 範囲をソートするクエリを素朴に実装するとO(NlogN)
実装
- ソートはどうやるんだ？
- あ、前回の図ではダメだ
- これはフェニック木に「断片のstartの値」が入ってるが、実際のソートやスワップのクエリは「配列上の位置」に対して掛かる
- それが検索できないといけない
- むしろ前後の値はフェニック木の二分探索で手に入るからリンクトリストが要らないのでは
- startとendの差から「次の断片」がどこにあるかは定数オーダーでわかる
- フェニック木の実装が1-originなのが混乱を招いたのでインターフェースを0-originにした
- 場合わけが大変で混乱してきた
一旦中断
ネットで解説を探すともっとシンプルにやってそうな感じ
スワップされたところを記録しておいて、ソートの時にはそこだけを確認すれば良い
ほんとにそうなのかいまいち自信が持てないけどその方針で実装してみよう
サンプルは通ったがジャッジは11TLE
一度立てたフラグを消してない
消すとサンプルが通らなくなる
- バグってるのにフラグを消してなかったことでたまたま通ってただけ
スワップの結果、手前に転倒が発生することがある
スワップの際(ソートの時に行われるものも含め)転倒しうるところにフラグを立てる
ソートはフラグを消しながら行う
これでACした
AC: python
def 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 values