哪位学长能跟我讲讲扫描线中的线段树维护
查看原帖
哪位学长能跟我讲讲扫描线中的线段树维护
1008172
duanzx楼主2024/9/1 13:38

O(n^2)的扫描线大致原理我是懂了

那么根据原理,需要用线段树维护区间中被覆盖次数大于0的线段总长度

每扫描一次需要对[l,r]的区间都需要加1或减1,按照线段树的区间修改的办法,要做一个懒标记

然后,查询[1,n]中大于0的线段总长度,但查询时如果遇到一个懒标记,如何通过懒标记得到这个区间的覆盖次数大于0的线段总长度?翻了一下,题解里面都没有对于这个的详细说明

2024/9/1 13:38
加载中...