GDKOI2021 TG Day2T2 island (以及一些線段覆寫最左端點的碎碎念)

題面描述

給出n個點，有向邊((i, i+1) in E), ((i, a_i) in E)

(a_i)會動态修改，求對于一個點(x)能到達的編号最小端點。

轉化

經過觀察發現，其實就是求線段集合 ([a_i, i])中(x)通過兩兩相交的區間到達的左端點。

解法

正着想不好想，我們試圖求出第一個不被線段覆寫的點。

發現線上段樹上維護被覆寫次數即可。

總結

正難則反？