【李超线段树】【学习笔记】

问题引入

Segment

对于区间修改操作，可以联想到线段树。但是容易发现标记（即同一个区间内的两条线段）并不能快速合并。
于是我们可以采用标记永久化，即李超线段树。

算法步骤

0. 线段树每个节点保存:区间范围(l,r),一条线段(k,b,id)

struct node{
	int l,r,id;
	double k,b;
}t[N<<1];

1. 单点查询操作
   从线段树的根节点一直递归到所查询的叶子节点，沿途把每个节点所记录的线段在所查询的x坐标的对应值累计到答案中。最后返回即可。

int query(int x,int pos,double val,int ans)
{
	if(t[x].l==t[x].r){
		return t[x].k*(double)pos+t[x].b>val||(t[x].k*(double)pos+t[x].b==val&&t[x].id<ans)?t[x].id:ans;
	}
	if(val<t[x].k*(double)pos+t[x].b||(val==t[x].k*(double)pos+t[x].b&&t[x].id<ans)){
		val=t[x].k*(double)pos+t[x].b;
		ans=t[x].id;
	}
	int mid=t[x].l+t[x].r>>1;
	if(pos<=mid) return query(x<<1,pos,val,ans);
	return query(x<<1|1,pos,val,ans);
}

2. 插入线段
   首先第一步与普通线段树相同，先将所插入的区间在线段树上划分为不超过logN个区间。
   第二步对于每个区间要插入一条线段：
   若该区间未记录过线段，则直接记录该线段并返回；
   若该区间所记录的线段完全不如该线段优，则将该区间的线段替换为该线段，并返回；
   若该区间所记录线段完全比该线段优，则直接返回；
   否则，则两线段有且仅有一个交点，则将当前节点的线段更改为非交点所在的子区间中最优的线段，并在交点所在的子区间中递归插入另一条线段。

void update(int x,double k,double b,int id)
{
	t[x].k=k,t[x].b=b,t[x].id=id;
}
void change(int x,int l,int r,double k,double b,int id)
{
	if(t[x].l>=l&&t[x].r<=r)
	{
		if(t[x].id==0) {
			update(x,k,b,id);
			return;
		}
		double y[2][2],X[2];//y的第一维表示旧/新线段，第二维表示左/右端点
		X[0]=(double)t[x].l,X[1]=(double)t[x].r;
		y[0][0]=t[x].k*t[x].l+t[x].b,y[0][1]=t[x].k*t[x].r+t[x].b;
		y[1][0]=k*t[x].l+b,y[1][1]=k*t[x].r+b;
		if(y[1][0]>=y[0][0]&&y[1][1]>=y[0][1]){
			update(x,k,b,(y[1][0]==y[0][0]?min(id,t[x].id):id));return;//注意在线段完全相同时，要保存编号较小的
		}
		if(y[1][0]<=y[0][0]&&y[1][1]<=y[0][1]) return;
		double mid=(X[0]+X[1])/2.0,pos=(b-t[x].b)/(t[x].k-k);
		if(pos<=mid) {
			if(y[1][0]>y[0][0]) change(x<<1,l,r,k,b,id);
			else change(x<<1,l,r,t[x].k,t[x].b,t[x].id),update(x,k,b,id);//注意为了防止信息覆盖，要先递归，再更新当前点信息
		}
		else
		{
			if(y[1][0]>y[0][0]) change(x<<1|1,l,r,t[x].k,t[x].b,t[x].id),update(x,k,b,id);
			else change(x<<1|1,l,r,k,b,id);
		}
		return;
	}
	int mid=t[x].l+t[x].r>>1;
	if(l<=mid) change(x<<1,l,r,k,b,id);
	if(r>mid) change(x<<1|1,l,r,k,b,id);
}

另外，对于垂直于x轴的线段，直接转化为一个斜率为1的点即可。