考察
apple(T_i,X_i)を取れるbasket start(S,L)はS∈[max(1,T_i-D+1),T_i]かつL∈[max(1,X_i-W+1),X_i]というaxis-aligned rectangleになる。
求める値は全apple rectangleに覆われる格子点(S,L)の最大重なり数である。
Sを昇順sweepすると各rectangleは開始時にL区間へ+1、終了直後に−1するrange-add eventへ変わる。
採用する候補: S方向をevent sweepし、L軸のrange add・global maxをlazy segment treeで管理する。
棄却する候補: 全(S,L)格子へ2次元imosを作る。
両座標が2×10^5でgridが約4×10^10 cellになりmemoryを持てない。
棄却する候補: 各Sでactive appleの全L候補をscanする。
時刻ごとに最大Xまで走査すると座標範囲の積に比例する。
各appleについてs0=max(1,T_i-D+1)、l0=max(1,X_i-W+1)を求め、events[s0]へ(+1,[l0,X_i])、events[T_i+1]へ(−1,同区間)を登録する。全L位置を0で持つrange-add/global-max lazy segment treeを作り、S=1..max T_iでその時刻のeventを全てapplyした後、root最大値でanswerを更新する。
典型の発動条件
rectangle overlapのsweep line
発動条件: 二次元axis-aligned rectangleの最大被覆数を求め、一軸のevent端点が離散的なとき。
一軸sweep+他軸range addへ変換する。
range add・range max lazy tree
発動条件: intervalへ増減を加えながら全位置の最大値を繰り返し問うとき。
node maxとadd lazy tagを持つ。
inclusive intervalの差分event
発動条件: 整数時刻[start,end]だけ対象をactiveにしたいとき。
startで追加しend+1で削除する。
問題固有の要素
basket配置を直接探索せず、各apple側から「自分を取れる配置parameterのrectangle」を塗るdualな見方で最大取得数が重なり最大へ変わる。
別の問題へ持ち帰る視点: 選択parameterで条件を満たすitem数最大化は、各itemが許すparameter領域を加算し最大被覆点を探す問題へ双対化する。
正当性
時間intervalはinclusiveなのでstart=max(1,T_i-D+1)で+1、T_i+1で−1を発生させると、S=T_iまでactiveになる。 空間intervalもLの整数候補に対するinclusive範囲で、segment treeでは[lower,X_i+1)へ変換する。 二次元rectangle加算を1次元の動的区間加算へ落とし、各appleを追加・削除の2回だけ処理できる。
実装上の注意
- 同じSに追加・削除があっても全eventを適用してからmaxを読むと、そのSでactiveなinclusive条件になる。
- Lは正整数だけなのでlowerを1でclipし、half-open segment tree indexへの変換を統一する。
復習の核
- D=W=1のappleが単一点(S,L)だけを覆う例と、終了T_i+1で削除される例をevent表にしてoff-by-oneを確認する。
計算量と制約
時間
O(N log N+N log X)、event sort版、Xは位置域の木size。全時刻走査版は追加O(Tmax)。
空間
O(N+X)、lazy tree。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N\leq 2\times 10^5; 1 \leq D\leq 2\times 10^5; 1 \leq W\leq 2\times 10^5; 1 \leq T_i\leq 2\times 10^5; 1 \leq X_i\leq 2\times 10^5; All pairs (T_i,X_i) are different.; All input values are integers.
出典