ABC 360 F — InterSections

考察

選ぶ区間の両端を同時に決めようとすると、候補の組が多すぎる。一方、一つの入力区間と交差する条件だけなら、両端がどこに入ればよいかを書き下せる。そこで、選ぶ両端を平面上の点と見て、交差する入力区間の数を「その点を覆う領域の数」へ読み替える。

交差条件から二つの長方形を作る

座標の上限を U=109U=10^9 とし、選ぶ整数の両端を 0≤l<r≤U0\leq l<r\leq U とする。入力区間 [Li,Ri][L_i,R_i] と交差するのは、端点が交互に並ぶ次の二通りである。単に区間が重なるだけでは足りず、包含や端点の一致は数えない。

Li<l<Ri<rまたはl<Li<r<RiL_i<l<R_i<r \quad\text{または}\quad l<L_i<r<R_i

各不等号を整数の閉区間へ直すと、点 (l,r)(l,r) が入る領域はそれぞれ

[Li+1,Ri−1]×[Ri+1,U][L_i+1,R_i-1]\times[R_i+1,U]
[0,Li−1]×[Li+1,Ri−1][0,L_i-1]\times[L_i+1,R_i-1]

となる。ここで積の左側は ll の範囲、右側は rr の範囲である。どちらかの範囲で下端が上端を超える長方形は捨てる。非空なら、第一の長方形では l≤Ri−1<Ri+1≤rl\leq R_i-1<R_i+1\leq r、第二では l≤Li−1<Li+1≤rl\leq L_i-1<L_i+1\leq r なので、長方形内の全点で l<rl<r が成り立つ。また、同じ入力区間から作った二長方形は互いに重ならず、一つの区間を二重に数えることはない。

例えば入力区間が [1,4][1,4] なら、二領域は [2,3]×[5,U][2,3]\times[5,U] と {0}×[2,3]\{0\}\times[2,3] になる。前者は右へはみ出す交差、後者は左へはみ出す交差に対応する。以後は、こうして残った高々 2N2N 個の長方形の被覆数を最大化すればよい。

左端を動かし、右端ごとの被覆数を保つ

非空の長方形を一般に [a,b]×[c,d][a,b]\times[c,d] と書く。左端 ll を小さい順に動かすと、この長方形が被覆数へ寄与するのは a≤l≤ba\leq l\leq b の間だけである。そこで、次の二つのイベントを作る。

  • l=al=a で、右端の範囲 [c,d][c,d] に +1+1 する。
  • l=b+1l=b+1 で、同じ範囲に −1-1 する。

この規約では、同じ ll の追加・削除をすべて反映してから答えを読む。更新後の値は、その ll で有効な長方形の被覆数を表す。

ll の走査候補は、00 と全長方形の a,b+1a,b+1 を集め、重複を除いて昇順に並べた集合とする。調べるのは 0≤l<U0\leq l<U の座標だけでよい。隣り合うイベント座標の間では有効な長方形が変わらないため、各整数区間の最小座標だけ調べれば、その範囲の最大値と最小の ll を保てる。最大のイベント座標以降も状態は一定であり、その座標を調べれば足りる。

右端の候補も O(N)O(N) 個にできるが、それらを毎回すべて調べると O(N2)O(N^2) になる。必要な操作が「区間への加算」と「全体の最大値および最小の達成位置」なので、右端側を座標圧縮し、遅延セグメント木で管理する。

圧縮するのは被覆数が一定の区間

右端の合法範囲は 1≤r≤U1\leq r\leq U である。圧縮用の座標集合を、各長方形の右端側の開始点と終了の次の点から

Y={1,U+1}∪⋃[a,b]×[c,d]{c,d+1}Y=\{1,U+1\}\cup\bigcup_{[a,b]\times[c,d]}\{c,d+1\}

と定める。重複を除いた昇順列を y0<y1<⋯<yK−1y_0<y_1<\cdots<y_{K-1} とする。セグメント木の葉 jj は、半開区間 [yj,yj+1)[y_j,y_{j+1}) に含まれる整数、すなわち yj,…,yj+1−1y_j,\ldots,y_{j+1}-1 を代表する。葉の数は K−1K-1 個であり、U+1U+1 自体には葉を作らない。

すべての加算範囲の境界を含めたので、一つの葉の中で被覆数は一定である。その葉を選ぶなら最小の実座標 r=yjr=y_j を返せばよい。セルの幅を被覆数に掛ける必要はない。求めるのは被覆された点の総数ではなく、一点での被覆数の最大値だからである。

座標 c,d+1c,d+1 の添字をそれぞれ p,qp,q とすれば、整数閉区間 [c,d][c,d] の更新は葉の添字の半開区間 [p,q)[p,q) への加算になる。例えば [1,4][1,4] だけから長方形を作る場合、Y={1,2,4,5,U+1}Y=\{1,2,4,5,U+1\} となる。l=0l=0 で加算する範囲 [2,3][2,3] はセル [2,4)[2,4) 一つに対応し、最小の右端は r=2r=2 と復元できる。

各葉の初期値は被覆数 00 と実座標 yjy_j の組とする。木の各節点には「最大被覆数と、それを達成する最小実座標」を持たせる。子の結合では被覆数が大きい方を採用し、同じなら実座標が小さい方を採る。区間加算では最大被覆数に加算し、達成位置は変えない。遅延値の合成は加算である。これにより、根から現在の最大値と最小の右端を取り出せる。

辞書順最小の答えを取り出す

記録する最大値を 00、答えを (0,1)(0,1) で初期化する。各候補 ll で全イベントを反映した後、根の最大被覆数が記録値を厳密に上回るときだけ、答えを現在の ll と根の最小実座標で置き換える。同率なら、既に記録した方の ll が小さいので更新しない。

木には r≤lr\leq l の座標も残っているが、正の被覆を持つ点は必ずいずれかの長方形内にあり、そこでは l<rl<r が保証される。従って最大値が正なら根の最小実座標をそのまま使える。最大値が 00 の間は根の位置を答えに使わず、合法な最小の組 (0,1)(0,1) を保つ。これで、ll に応じて木の探索範囲を変える必要がなくなる。

典型の発動条件

長方形被覆の平面走査

二つの未知数への条件が軸平行長方形へ分解でき、条件を満たす入力の個数を最大化したいときに使う。一軸を固定すると残る条件は一次元区間になり、その区間の有効期間を追加・削除イベントに変えられる。

最大値と最左位置のlazy segment tree

区間加算の下で、最大値に加えて同率時の最小座標を求めたいときに使う。区間内の全値へ同じ数を足しても最大の達成位置は変わらないため、最大値と最小位置の組を遅延評価できる。圧縮後は、葉の添字と答えに出す実座標を区別する。

問題固有の要素

区間の端点が交互に並ぶという条件に注目すると、未知区間の両端を点と見たときの領域が、重ならない二長方形になる。さらに、各長方形が丸ごと l<rl<r を満たすので、正の最大被覆を探す段階では斜めの境界を管理しなくてよい。

別の問題でも、複数の未知数を同時に選ぶのが難しければ、まず一つの入力が寄与する未知数の範囲を描いてみる。条件を満たす点の領域が単純なら、入力ごとの領域被覆へ変換できる。

正当性

整数の狭義不等式を閉区間へ直して得た二長方形は、各入力区間との交差条件を過不足なく表す。同じ入力区間の二領域は互いに素なので、合法な点での長方形の被覆数は、交差する入力区間の数に等しい。空領域を捨てても寄与する点は失われない。

走査中、長方形の開始座標で加算し、終了座標の次で減算する。同座標の全差分を反映した後の各葉は、現在の左端で有効な長方形による被覆数を保持する。右端側の全境界を圧縮集合に入れたため、一つの葉の全整数は同じ被覆数を持ち、葉の左端がその中の最小の右端となる。従って根は、固定した左端での最大被覆数と最小の達成位置を返す。

左端側もイベント間で被覆数が変わらないので、各範囲の最小座標を調べれば十分である。正の最大被覆を達成するセルは少なくとも一つの長方形に含まれ、セル内では左端が右端より小さい。よって各軸の最小座標を代表にしても、合法な最適解を失わない。

左端の昇順に調べ、記録値を厳密に上回る場合だけ答えを更新するため、最終的な最大値を達成する最小の左端が残る。そのとき根は最小の右端を選ぶので、答えは辞書順最小である。最大被覆数が0なら全ての合法な組の交差数が0であり、初期値の組が辞書順最小の答えとなる。

実装上の注意

  • 空判定は各長方形の両軸で行う。Ri=Li+1R_i=L_i+1 なら内側に置ける整数がなく、両長方形とも空になる。Li=0L_i=0 なら第二の長方形、Ri=UR_i=U なら第一の長方形が空になる。全領域が空でも、Y={1,U+1}Y=\{1,U+1\} と走査候補 l=0l=0 は残る。
  • 入力に同じ区間が複数あれば、それぞれ別の寄与としてイベントを残す。圧縮座標の重複は除くが、イベントの重複は除かない。
  • 同座標の追加と削除の途中で根を読むと、実際には同時に有効でない長方形を数えかねない。全更新を終えた状態だけを比較する。
  • U+1U+1 は r=Ur=U を含むセルの右境界を表す番兵であり、出力候補ではない。木を2の冪まで埋める実装では、余分な葉を最大値の候補へ混ぜないよう、被覆数を負の無限大とする。
  • 被覆数は高々 NN である。座標は終了の次の点まで保持し、圧縮添字ではなく保存した実座標を出力する。

復習の核

  • 二変数の全探索が難しければ、一つの入力が寄与する領域を二変数の平面に描く。
  • 整数閉区間をイベントにするときは「開始で追加、終了の次で削除」と決め、同座標の全差分を反映してから読む。
  • 座標圧縮で最小解も復元したいなら、値が一定のセルと、その最小実座標を対応付ける。
  • 木が扱う点に不適なものが混ざる場合、正の寄与を持つ点の合法性と、最大値0の扱いを分けて確認する。

計算量と制約

時間

O(Nlog⁡N)O(N\log N)。長方形は高々 2N2N 個、イベントは高々 4N4N 個で、両軸の候補数も O(N)O(N) 個である。イベントと圧縮座標の整列に O(Nlog⁡N)O(N\log N)、木の構築に O(N)O(N)、各イベントの区間加算に O(log⁡N)O(\log N) を使う。各走査候補で根を読む費用は O(1)O(1) であり、全体も O(Nlog⁡N)O(N\log N) となる。

空間

O(N)O(N)。入力、長方形、イベント、圧縮座標と遅延セグメント木はいずれも O(N)O(N) 個の要素を保持する。座標上限 UU に比例する配列は作らない。

制約との対応

1≤N≤1051\leq N\leq 10^5、0≤Li<Ri≤1090\leq L_i<R_i\leq 10^9 で、入力は全て整数である。整数であることを使って狭義不等式を端点の ±1\pm1 へ直す。座標の広さによらない O(Nlog⁡N)O(N\log N) 時間・O(N)O(N) 空間の処理とし、公式の時間制限2秒・メモリ制限1024 MiBに対応する。

出典

分類・前提・執筆情報

掲載状態: 収録済み

InterSections の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: event順にactive集合を更新する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: event・値順のオフライン走査

    補助タグ: 座標・値の順序保存圧縮 遅延評価する区間作用

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: event順にactive集合を更新する

    • 値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。

    先に読む単元:

    この解説で扱わないこと:

    • 更新を単に逆順へ読む処理、答えの局所寄与だけを集計する順序交換、sort-uniqueしたkeyの添字化、および固定方向の単純scan。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題