Educational Codeforces Round 13 F. Lena and Queries

以下の 3 種類のクエリを処理せよ。

クエリを B=√n 個ごとに分解する。あるクエリ群[i,i+B) を処理することを考えよう。

クエリ群 [0,i) を処理したあとの集合を A とする。この中からクエリ群 [i,i+B) に関係する点をすべて集合 B に移す。こうすることで、クエリ群[i,i+B) を処理する間は集合 A は不変になる。クエリ群[i,i+B) の処理は集合 B に対して行う。

集合 A は不変なので、集合 A の最大値を求めるのには凸包が使える。集合 B の方は追加や削除が頻繁に起こるが、サイズが O(√n) なので全探索しても O(√n) で最大値が計算できる。集合 A の最大値を集合 B の最大値のうち大きい方が答えとなる。

全体の計算量は O(n√n)。結構厳しい。

動的に凸包が作れれば解ける。追加だけなら簡単で、削除があっても一応 O(log² n) で処理できる。

雰囲気は次の PDF を参考に。

凸包の分割統治を平衡二分探索木を使ってサクサクやるだけだが、短時間コンテスト中に実装するものではないし、定数も結構重い。

適当に書いたら merge/split と共通接線の負荷が尋常じゃなかったので、平均的に負荷が減るように誤魔化している。一応今回の問題は 1325 ms で通ったが hackケースとかあるかも。

平方分割には気付いていたが、最近書いた動的凸包を verify したくて動的凸包で通した。