(CodeChef December Challenge 2018) Colorblind Feast
問題概要
あなたは空の配列と定数Kを持っている。以下のクエリをQ個処理せよ。
- 1 c d : [更新クエリ] 先頭に色c, よさdのモノを追加する
- 2 c d : [更新クエリ] 末尾に色c, よさdのモノを追加する
- 3 c : [質問クエリ] 現在の配列から色が[c-K,c+K]内にあるモノだけを残して、それ以外を取り除き、空いたところを詰める。残ったモノのよさdの区間和の最大値を求め、取り除いたモノを元に戻す。
制約
1 <= Q <= 2*10^5
1 <= c,K <= 10^9
|d| <= 10^3
cの値は直前の質問クエリの答えがわからないと求められない
解法
問題で与えられた通りの配列をそのまま持つと質問クエリで時間がかかってしまう。
まず、色を無視して、配列の区間和の最大値を高速に求めることを考えてみる。
先頭にモノを追加したとき、区間和の最大値はどう変化するか？
変化するとすれば、その値は、先頭に追加したモノを含む区間の和の最大値になるはず。
そこで、追加前の区間和最大値ansと、追加前の先頭から連続した区間の和の最大値frontmaxの情報を持っていれば、
ans = max(ans, d+frontmax)
frontmax = max(d+frontmax, d)
というように更新できる。
末尾に追加する場合は、追加前の末尾から連続した区間の和の最大値backmaxを持っていればよい。
これによって、配列の中身をそのまま持つことなく、時間Ο(1),空間Ο(1)で区間和最大値を求めることができる。
区間和最大値をこのように更新していくためには、それぞれの質問クエリに関係ないモノをそれぞれ無視しなければならない。
つまり、質問クエリの引数それぞれについて上のような情報を持ち、上のような更新を行っていかなければならない。
これを愚直にやっても、更新クエリの数はQ個であるから、Ο(c_max*Q)かかって間に合わない。
色xのモノが影響を与える質問クエリは、引数が[x-K,x+K]内にあるようなクエリのみだから、上のような情報を引数の大小で並べて保持していると、区間に対して更新していくことができる。
セグメント木が使えそう。
更新クエリが来たときは区間を更新し、質問クエリが来たときは点が含まれる区間を順に見てansを出力する。
遅延評価のように、区間に対しての更新を考えると、モノはどこかのノードで積もることになる。質問クエリそれぞれについて積もったこれらを1つ1つ順番に追加しているようでは、セグ木を使ってないときと変わらず遅くなってしまうから、モノの列とモノの列を高速にマージしなければならないことがわかる。
これは、ansとfrontmaxとbackmaxのほかに、列全体の和totalを保持しておけば以下のようにマージできる。
列Fの末尾に列Bをマージするとき、
ans = max(ans, F.backmax+B.frontmax)
F.frontmax = max(F.frontmax, F.total+B.frontmax)
F.backmax = max(B.backmax, F.backmax+B.total)
F.total = F.total+B.total
とすればよい。
これによって時間Ο(Qlog(c_max))ですべてのクエリを処理することができる。
両側についてこのように更新を行うセグ木を実装すればよいが、面倒なので、それぞれの側に関してセグ木をもち、質問クエリ処理の最後に双方をマージすることにした。
以上より時間は改善できた。が、セグ木の空間Ο(c_max)はやばい。
すべての質問クエリの引数cがあらかじめわかっていれば、座標圧縮すればいいのだが、この問題は前の質問クエリの答えがわかっていないとcがわからない。
10^9個程度の配列はさすがに取れないから悩んでいたが、セグメント木の必要な部分だけのメモリを保持し、それ以外はメモリ取得をサボるというアイデアを知った。
以下の13~14ページ目に記載されている。
プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～
これを自力でいい感じに実装すれば、空間もΟ(Qlog(c_max))となる。
ほんとうは平衡2分木を書かなくちゃならないのかと思っていたが、これのおかげで命拾いした。
ソースコード
