APIO2018 New Home

問題概要

一次元の座標がある。1~Kの色の店が指定された座標に現れたり消えたりするので、色別にある座標から最も近いものまでの距離を求めその最大値を取った値を答える。

クエリは先読み可。

解法

Subtask1

N,Q<=400

時の流れを時系列に、計算クエリ毎にO(N)かけて距離を計算。全体でO(NQ)。

Subtask2

N,Q<=60000,K<=400

時の流れを時系列に、色ごとに店の座標のsetを管理する。計算クエリでは色ごとにset.lower_boundをする。O((N+QK)logN)

Subtask3

N,Q<=300000,店はすべて最初から最後まで存在する

時の流れの存在意義がなくなるので、座標の昇順(対称性より降順でも可)を時系列に取る。それぞれの色で、最も近いものまでの距離は「x+定数」か「-x+定数」の形の関数がその色の店の個数の二倍の個数並んでいる形になるので、それらのうち最適なものがどれかが正しい状態になるようにする。「x+定数」、「-x+定数」のそれぞれの定数の値の候補をsetで管理して、O((N+Q)logN)

Subtask4

N,Q<=300000,店はすべて最初存在し、しだいになくなっていく

何もわからない

Subtask5

N,Q<=60000

Subtask2の手法とSubtask3の手法を組み合わせて、クエリの平方分割をする。

時の流れの時系列に、B(=バケットサイズ)個ごとにクエリを処理する。その期間中にその色の店が現れたり消えたりするような色については、Subtask2の方法を用いて最短距離を計算する。そうでない色については、その期間中常に存在している店だけをピックアップして、Subtask3の方法を用いて最短距離の最大値を計算する。N=Qとすると計算量はO(ANlogN+BNlogN)になって、A=B=√NとすればO(N√NlogN)になる。

しかし、setを使っているO(N√NlogN)なので非常に厳しい。バーチャルでこれを提出したところ、一ケース目から間に合わなかった。

Subtask6

N,Q<=300000

時の流れを時系列に取る。計算クエリでははじめに答えを二分探索し「ある座標の区間内にすべての色が存在するか?」という問題に変形する。

これはセグメント木の基本的な問題である。各店の座標の地点には直右の同色の店の座標を置く。店の追加、削除は色ごとに店の座標のsetを管理しておき、lower_boundで変化した地点のひとつ左とひとつ右を見て、2回くらいセグメント木の一点更新をする。区間[L,R]内にすべての色が存在するかは、[-∞,L-1]のmaxがR以下であるかに等しい。計算量はO(Nlog^2N)。TimeLimitが5秒なので間に合う。二分探索をダブリングでする(セグ木上で二分探索するテク)とO(NlogN)になるが、座標圧縮などの関係で実装は大変になる。

それぞれの色でかなり左の方にひとつずつ店があると仮定して、座標そのものが同じでも店によって違うセグメント木の地点を割り当てるとすると実装が楽になる。

ソースコード

oj.uz