扫描线和区间问题

用扫描线把静态二维问题转换成一维动态问题。

首先是最基本的形态

•给一个长为n的序列，有m次查询，每次查区间中<x的元素个数

看起来和扫描线有什么关系？？

比如说一组数据，1，5，3，4，我们以下标为x轴，值为y轴，可以得到

假如我们要询问位于[2,3]中小于4的元素数量，我不就是想知道

这个矩形当中的点的数量嘛？

这种思想推广一波，就得到了二维数点问题

P2163 [SHOI2007]园丁的烦恼

把所有的询问离线下来然后扫描线一波。

这能不能推广的更抽象一些，比如一个区间询问？

假如我们知道一个点的坐标是x，y，我们以l为横坐标，y为纵坐标，那么一个点会被哪些区间包含？考虑取值范围，可以知道，就是它左上方的一个矩形。

这样就可以把区间问题搞成二维问题了。