読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Educational Codeforces Round 13 F. Lena and Queries

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

問題

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

  • 点 (x,y) を set に追加する
  • i 番目のクエリで追加した点を set から削除する
  • xq+y の最大値を求める

考察

  • 解は点集合の凸包の上側の点のどれか。
  • 凸包は凸なので二分探索で最大値を求められる。

解法(平方分割)

クエリを 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)。結構厳しい。

Educational Codeforces Round 13 F. Lena and Querie ...

解法(動的凸包)

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

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

https://cw.fel.cvut.cz/wiki/_media/misc/projects/oppa_oi_english/courses/ae4m39vg/presentations/ko-overmars-fuksa.pdf

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

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

Educational Codeforces Round 13 F. Lena and Querie ...

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