https://www2.ioi-jp.org/joi/2023/2024-ho/

まずはこちらから公式解説を読んでください。

公式解説にあるように、結局以下の \(2\) つが高速に求まればいいです。

• \(S_{i}\) : 区間 と共通部分を持つ区間の番号のうち、 \(i\) 未満で最大のもの（ないならば ）

• \(T_{i}\) : 区間 と共通部分を持つ区間の番号のうち、 \(i\) より大きくて最小のもの（ないならば ）

公式解説では lazy segment tree を用いていましたが、 セグメントツリーを用いて求めます。

\(S_{i}\) の求め方のみ記します。 (\(T_{i}\) は順番を反転させれば同様に求まる。)

区間 \(i\) と共通部分を持つ区間 \(j\) は以下のいずれかの条件を満たします。

• \(B_{i}<A_{j}<A_{i}\)
• \(B_{j}<A_{i}<A_{j}\)

この \(2\) つの条件ごとに、 \(S_{i}\) の候補を探します。

• \(B_{i}<A_{j}<A_{i}\) について

長さ \(2N\) の数列 \(C=(C_{1},C_{2},\dots C_{2N})\) を全て \(0\) で初期化します。

\(i=1,2,\dots N\) の順に、以下の操作をします。

\(S_{i}\leftarrow \max(S_{i},\max(C_{B_{i}},C_{B_{i}+1},\dots C_{A_{i}}))\) と更新した後、 \(C_{i}\leftarrow i\) と更新する。

これらの操作は、セグメントツリーを用いて高速に計算できます。

• \(B_{j}<A_{i}<A_{j}\) について

集合 \(D\) を空の状態で初期化します。

\(i=1,2,\dots 2N\) の順に以下の操作をします。

• \(A_{k}=i\) を満たす \(k\) が存在するとき、その \(k\) を用いて、 \(D\) に \(k\) を挿入する。
• \(B_{k}=i\) を満たす \(k\) が存在するとき、その \(k\) を用いて、 \(D\) から \(k\) を削除した後、\(D\) に含まれる \(k\) 以下の最大の整数が存在するならそれを \(a\) として、 \(S_{k}\leftarrow \max(S_{k},a)\) と更新する。

これらの操作は std::set を用いて高速に計算できます。

以上 \(2\) つの条件に対する計算は、どちらも時間計算量 \(O(N\log(N))\) で実行できます。