扫描线学习笔记

扫描线

扫描线是重要的思想，能解决的问题诸如：区间覆盖点数，区间询问（一般不可修改），侧重考虑构思：加点，解决左端点。

典例

典例一：模板扫描线

其实只要维护一个区间覆盖点数，再上左右扫一次，上下扫一次。

---

典例二：P8037 [COCI2015-2016#7]Prokletnik

重心在定右端点后考虑能扩展最左的左端点，搞完用树装数组维护后缀 $max$ 即可

同时只考虑大小关系可以用离散思想即本题典 $trick$。

---

典例三：P1972 [SDOI2009] HH的项链

重心在加点，考虑加的点的贡献要考虑左端点不能出错的构造寻找解题方案。

---

典例四：P4211 [LNOI2014] LCA & P5305 [GXOI/GZOI2019] 旧词

重心在加点，该 trick 以适用任意函数，即构造加点的构造函数，要考虑树上前缀加出来是每个点的函数。

---

典例五：P4137 Rmq Problem / mex

设计信息 & 考虑左端点，典的 $trick$，$O(n \log^2 n)$ 是简单的，$O(n \log n)$ 在线段树上二分，其形态如此：

int qry(int p,int l,int r,int val){
	if(l==r)return l;
	int mid=l+r>>1;
	if(t[ls]<val)return qry(ls,l,mid,val);
	else return qry(rs,mid+1,r,val);
}

至此得到静态区间 mex $O(n\log n)$ 做法。