Codeforces Round #397 F. Sourvenirs

高速化できたので追記しました。

http://codeforces.com/contest/765/problem/F

解法1

平方分割を用いた log のつかない解法ではあるが、どうみても重くて、実際実装したら重かった。2791 ms2168ms(書き直したら速くなった)。提出を見ると根本的に平方分割していない解が見えたがそっちはよく理解していない。

クエリを 3 つの区間に分解する。

f:id:pekempey:20170215183434p:plain

一番簡単なのが 3つ目のクエリで、あらかじめソートしておけるのでmergeを使ってO(√N)。

1つ目は x が√N通りなので、x 毎に O(N) で処理できればいい。linked-list を使う。linked-list に挿入するときに、どのノードの間に挿入すれば良いのかを知る処理が難しそうである。これを線形時間でやるには次のようなトリックを使う。

あらかじめ [x,n) の範囲で linked-list を作っておく。そして n-1,n-2,...,x の順にノードを削除していく。uを削除したとき、L[u]とR[u]の値をそのままにしておくのが鍵。x,x+1,x+2,...,n-1 の順に挿入していくのだが、このとき挿入するべき場所は L[u],R[u] に残っている。


解法2

linked-listのトリックとsnukeさんのmoを組み合わせる。1700ms。linked-listがundoできるのはそれはそうなんだけど、追加情報なしでいけるってのが面白い。あと undo を使って min を求めるってのも面白い。