当前位置:首页 > 数据结构 > 线段树 > 正文
GDKOI2021提高组Day2B群岛
47+

题目大意:n个相邻的岛屿,每个岛屿有一条向右走的路,还有一条到达另一个岛屿的路,这条路可以动态修改,请问某个岛屿最左可以到达哪个位置?

解题思路

显然,右边的岛屿均可到达,往左走需要靠“反向边”,如果每条反向边看成一条线段,那么线段合并后,左端点即最左边的位置。

如岛屿5可以到达岛屿3,岛屿6可以到达岛屿7,岛屿8可以到达岛屿4,那么岛屿3~8都可以到达岛屿3!

对于修改操作,我们可以看出是区间减、区间加,先减去之前线段的影响,再加上当前新的线段。

我们可以用线段树维护区间最小值,然后查找区间第一个1的位置(断开位置)即可!

我们可以用二分查找线段树区间最小值,也可以直接用线段树的二分查找!

程序实现

GDKOI2021提高组Day2B群岛:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter