扫描线学习笔记

伞兵二号zja · 2022-02-18 22:17:36 · 个人记录

问题引入：计算矩形面积并

考虑对于每个y，统计x坐标上有哪些被矩形覆盖了。引入扫描线概念。

扫描线截得若干线段，随扫描线y值改变而改变。

对每个矩形的上下边排序，然后从小到大枚举y值。

碰到矩形下边时，区间+1，碰到上边时，区间-1。

统计当前y值的[1,30000]中有多少个数>0。

可以转为统计0的个数，也就是最小值的个数，用30000减去。

维护一个支持区间加减、统计最小值个数的线段树，时间复杂度(n log n)。

线段树中：tag表示当前节点表示的区间每个数加上的值，

min表示区间最小值，cnt 表示最小值的个数。

pushdown函数不用做改动，pushup函数可以是：

void pushup(int x) {
    Min[x] = min(Min[ls], Min[rs]);
    if(Min[ls] == Min[rs]) {
        Min[x] = Min[ls];
        cnt[x] = cnt[ls] + cnt[rs];
    }
    else {
        Min[x] = Min[ls] < Min[rs] ? Min[ls] : Min[rs];
        cnt[x] = Min[ls] < Min[rs] ? cnt[ls] : cnt[rs];
    }
}

当问题规模扩大，如 0<x,y<10^9，就不能直接对横坐标建树了。

运用离散化思想，由于不同的x坐标只有2n个，不妨将他们排序映射到[1,2n]，这样就可以建树了。注意计算答案时要用原来的x和y。

开一个'event'数组，记录y值对应的需进行的区间加减操作。按顺序加入其中。

建树时应另外开一个变量存储本节点原来对应的线段长。