概要
公式解説も面白いけど、こっちの方が分かりやすいかな？
解法
解説同様に、次のように辺を張ったグラフを作って強連結成分分解すれば解くことができます。
- $i<j$ かつ $R_i +i \geq L_j + j$ のとき、$i\to j$
- $i<j$ かつ $L_i-i\leq R_j-j$ のとき、$j\to i$
分割統治で解きます。区間 $[l, r)$ に対する処理は、$m = \lfloor(l+r)/2\rfloor$ とするとき次のようになります。
- $[l, m)$, $[m,r)$ 内での辺を再帰的に張る
- $m$ をまたぐ辺を張る
$m$ をまたぐ辺、つまり $[l,m)$ と $[m,r)$ の間の辺を張るのですが、この部分について上手く辺の本数を減らせればよいです。
$i\to j$ 型の辺のみ説明します。$[l,m)$ 内の頂点を昇順に並べて $v_1, \ldots, v_{m-l}$ とすると、各 $j$ に入る辺を張る操作は「ある $k$ に対して、$v_k, v_{k+1},\ldots, v_{m-l}$ から $j$ に辺を張る」という形で表せます。これは、$v_{i+1}$ から $v_i$ に辺を張っておくことで、ひとつの辺で表現できます。
分割統治において、長さ $n$ の区間に対して $O(n\log n)$ 時間で $O(n)$ 本の辺を持つグラフを構築します。したがって、全体の計算量は $O(n\log^2n)$ 時間、グラフの大きさは頂点・辺の数とも $O(n\log n)$ となります。
