李超线段树

前言

T4正解李超线段树？不会，滚过来学

保留节目百度百科自学已被删除

讲解

貌似思路并不是很难的亚子

我们需要在线支持一下两个操作：

• 插入一条线段

• 给定(x_0)，询问当(x=x_0)时所有线段的最高点

我们可以使用权值线段树！

对于每个区间，我们维护一个最优线段

1.插入

显然对于一个线段完全覆盖的区间我们才处理

分四种情况讨论：

(1).当前区间无最优线段

直接赋值

(2).当前线段完全覆盖最优线段

直接赋值

(3).当前线段完全被最优线段覆盖

直接滚粗

(4).相交

最复杂的情况，我们考虑将覆盖该区间最长的线段保留为最优线段

欸嘿？怎么搞呢？其实只需判断该区间中点谁在上面就行了，中点位置在上面的线段一定是覆盖最长的线段

然后把另外一条丢到下面去接着修改

插入时间复杂度(O(log^2 n))

2.询问

一直往下走，对于每个走到的区间的最优线段求出一个函数值，取( exttt{max})即可

询问时间复杂度(O(log n))

练习

loj板题「雅礼集训 2017 Day2」线段游戏

代码

「雅礼集训 2017 Day2」线段游戏

const int M = 1000001;
const int MAXN = 2000005;
int n,Q;
struct line
{
	double k,b;
	bool f;
	line(){}
	line(double k1,double b1,bool f1){
		k = k1;
		b = b1;
		f = f1;
	}
};
#define lc (x<<1)
#define rc (x<<1|1)
double getf(line w,int x){return w.k * x + w.b;}
struct LiChaoSegmentTree
{
	line t[MAXN << 2];
	void Add(int x,int l,int r,int ql,int qr,line w)
	{
		int mid = (l+r) >> 1; 
		if(ql <= l && r <= qr)
		{
			if(!t[x].f) t[x] = w;
			else if(getf(w,l) >= getf(t[x],l) && getf(w,r) >= getf(t[x],r)) t[x] = w;
			else if(getf(w,l) <= getf(t[x],l) && getf(w,r) <= getf(t[x],r)) return;
			else
			{
				if(getf(w,mid) >= getf(t[x],mid)) swap(w,t[x]);
				if(getf(w,l) > getf(t[x],l)) Add(lc,l,mid,ql,qr,w);
				else Add(rc,mid+1,r,ql,qr,w);
			}
			return;
		}
		if(ql <= mid) Add(lc,l,mid,ql,qr,w);
		if(mid+1 <= qr) Add(rc,mid+1,r,ql,qr,w);
	}
	
	double Query(int x,int l,int r,int q)
	{
		double ret = -M;
		if(l <= q && q <= r && t[x].f) ret = getf(t[x],q);
		if(l == r) return ret;
		int mid = (l+r) >> 1; 
		if(q <= mid) ret = Max(ret,Query(lc,l,mid,q));
		else ret = Max(ret,Query(rc,mid+1,r,q));
		return ret;
	}
}st;

void AddLine()
{
	int x1 = Read() + M,y1 = Read(),x2 = Read() + M,y2 = Read();
	double k,b;
	if(x1 == x2) k = 0,b = Max(y1,y2);
	else k = 1.0 * (y2-y1) / (x2-x1),b = y1 - k * x1;
	st.Add(1,1,M<<1,Min(x1,x2),Max(x1,x2),line(k,b,1));
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n = Read(); Q = Read();
	for(int i = 1;i <= n;++ i) AddLine();
	for(; Q ;-- Q)
	{
		int opt = Read();
		if(!opt) AddLine();
		else 
		{
			double ans = st.Query(1,1,M<<1,Read()+M);
			if(ans == -M) Put(0,'
');
			else printf("%.2f
",ans);
		}
	}
	return 0;
}