线段树合并 – Tgotp-Blog

4631: 踩气球

对于每个点维护一下这个点能向右跑的最远距离,这个很显然能用并查集维护。

然后考虑每个点建一棵线段树,然后根据左右两点的关系合并线段树。

那么在记录的最远距离左边的点一定都是已经可以加入答案的点,删去即可。

c++代码如下:
[crayon-5bcea06b924bb0426274[......]

Read more