本文发表于 604 天前,其中的信息可能已经事过境迁

扫描线

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

典例

典例一:模板扫描线

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


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

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

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


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

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


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

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


典例五:P4137 Rmq Problem / mex

设计信息 & 考虑左端点,典的 trickO(nlog2n) 是简单的,O(nlogn) 在线段树上二分,其形态如此:

cpp
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(nlogn) 做法。