ABC217D - Cutting Woods - 競プロはじめました

C++ ではこんなに簡単にかけるのに．．．
Editorial - AtCoder Beginner Contest 217

一般的な話は次が役立ちそう：

考え方

ソート状態を保ったままカット位置cut = [0, ..., L]を保持できれば，$c=2$の場合に

pos = bisect.bisect_left(cut, x)
print(cut[pos] - cut[pos - 1])

と，長さが計算できる．

しかし，クエリを順に見ていき$c=1$の場合に

pos = bisect.bisect_left(cut, x)
cut.insert(pos, x)

や，（同じことだが）

bisect.insort_left(cut, x)

としていては間に合わない．

先にクエリを読み込み，切る位置をすべて把握・ソートしておけば，挿入せずにソート状態を保つことができる．

棒を切る問題にありがちな，バラバラな状態からつないでいく考え方．

カット位置をcutsで記憶
Union-Findで，「カット位置$i$の左側の棒」を管理
カット位置$i$の左側の棒（棒$i$と呼ぶ）の長さをsum[i]で記憶する．棒をつないだあとは，sum[root[i]]で棒$i$を含む棒の長さを管理する．

クエリを逆から見ていき，

$c=1$：
- クエリのカット位置と一致するものがcutsにあることに注意して，bisectでindexを取得．
- Union-Findで，棒を併合
- 併合した要素の根のindexのsum[root[i]]に棒の長さを保存
$c=2$：
- クエリを逆から見ているので，カット位置に一致する可能性があることに注意して，indexを取得する
- sum[root[i]]を答えのリストに保存する

最後に，逆順に答えを出力すれば良い．

クエリで問われる座標（$c=1,2$の両方）と$\{0,L\}$の集合を$X$とする．これを座標圧縮する（対応を辞書で$D[X[i]]=i$と表す）．

クエリで問われる座標の集合をセグメント木で管理する．座標$i$の状態を

\begin{aligned}
s_{i}=
\begin{cases}
\, 0 &(\text{切られていない場合}) \\
\, 1 &(\text{切られている場合})
\end{cases}
\end{aligned}

とする．

クエリを前から見ていき，

$c=1$：
- $D[x]=i$に対し，$s_{i}=1$とする．
$c=2$：
- $D[x]$までに何回切られているかを取得する（累積和）
- 切られている回数を初めて超えるindexを二分探索で取得する：左端の位置が$X[\mathrm{index}]$とわかる．
- 切られている回数 + 1を初めて超えるindexを二分探索で取得する：右端の位置が$X[\mathrm{index}]$とわかる．
- 上により，両端の位置がわかるので，長さが出力できる．