李超线段树

李超线段树

发现要维护的问题十分难做，所以我们要引入李超线段树。

我们发现，如果在一个区间内，一条线段的整体在另一条线段上方，那么这条线段一定更优，我们称之为最优线段。但是如果并不是这样，应该如何做呢？

这里给出线段为一个区间内的最优线段的条件：

• 线段的定义域覆盖了整个区间。

• 线段在区间中点的位置最高。

现在我们假设 \(l_1\) 为区间 \([l,r]\) 内的最优线段，我们要插入一条新的线段 \(l_2\)。

如果当前区间没有最优线段，或者 \(l_2\) 整体在 \(l_1\) 上方，那么可以直接用 \(l_2\) 替换 \(l_1\) 作为该区间的最优线段。

而如果 \(l_1\) 整体在 \(l_2\) 上方，那么显然 \(l_2\) 是劣的，不用再进行修改及递归。

最后是比较难的一种情况：如果两个线段谁也没有被谁完全压住，那么他们一定出现交点。

下面记区间中点为 \(mid\)。

我们比较两条线段在 \(mid\) 处的高度，更高的那条作为最优线段。但是，虽然剩下那一条线段在这个区间不是最优的，但是可能在子区间内最优，所以我们要进行递归，用更劣的那条线段更新子区间。

我们记 \(l_3\) 为更新子区间的线段（其实就是上面两条线段更劣的那一个）。我们对交点的位置进行分类讨论：

• 交点在 \(mid\) 左侧：画个图可以发现 \(l_3\) 只可能在左子区间成为最优线段，故递归左子区间。

• 交点在 \(mid\) 右侧：同理，递归右子区间。

• 交点在 \(mid\) 处：看 \(l_3\) 在 \(l\) 还是 \(r\) 的位置更高，就选择哪一边递归。

我们的基本思想就说完了，下面说一下作者在写这道题的时候遇见的错误：

• 把所有模数都看成 \(39989\)。

• 没有看到交点相同时要选择编号最小的线段。

既然是板子题，下面就放一下代码：

#include<bits/stdc++.h>
#define int long long
#define N 100005
#define mod1 39989
#define mod2 1000000000
#define eps 1e-8
using namespace std;
int cnt,res,tot,rt;
struct line{
	double k,b;
}a[N];
struct node{
	int ls,rs,id;
}w[N<<2];
bool check(int i,int j,int x){
	if(a[i].k*x+a[i].b-a[j].k*x-a[j].b>eps)return 1;
	if(a[j].k*x+a[j].b-a[i].k*x-a[i].b>eps)return 0;
	return i<j;//函数用于判断哪个线段更优 
}
void modify(int &u,int l,int r,int L,int R,int now){
	if(l>R||r<L)return;//完全无交 
	if(!u)u=++cnt;//动态开点 
	if(l>=L&&r<=R){//完全包含 
		if(check(now,w[u].id,l)&&check(now,w[u].id,r)){//新的线段更优，直接更新 
			w[u].id=now;
			return;
		}
		if(check(w[u].id,now,l)&&check(w[u].id,now,r)){//旧的线段更优，直接跳过 
			return;
		}
		int mid=l+r>>1;
		if(check(now,w[u].id,mid)){
			swap(now,w[u].id);//区间内最优线段 
		}
		if(check(now,w[u].id,l)){//用更劣的线段更新子区间 
			modify(w[u].ls,l,mid,L,R,now);
		}
		if(check(now,w[u].id,r)){
			modify(w[u].rs,mid+1,r,L,R,now);
		}
	}
	else{
		int mid=l+r>>1;
		modify(w[u].ls,l,mid,L,R,now);//不被完全包含，递归解决 
		modify(w[u].rs,mid+1,r,L,R,now);
	}
}
void solve(int u,int l,int r,int p){
	if(!u||r<p||l>p)return;//没有点或者完全无交 
	if(check(w[u].id,res,p)){//当前答案比之前的答案更优 
		res=w[u].id;
	}
	if(l==r)return;
	int mid=l+r>>1;
	solve(w[u].ls,l,mid,p);//递归解决 
	solve(w[u].rs,mid+1,r,p);
}
signed main(){
	int n,las=0;
	cin>>n;
	while(n--) {
		int op,x_0,y_0,x_1,y_1;
		cin>>op;
		if(op==0){
			int k;
			cin>>k;
			res=0;
			k=(k+las-1)%mod1+1;
			solve(1,1,mod1,k);//查询答案 
			las=res;
			cout<<res<<'\n';
		}
		else{
			cin>>x_0>>y_0>>x_1>>y_1;
			x_0=(x_0+las-1)%mod1+1;
			y_0=(y_0+las-1)%mod2+1;
			x_1=(x_1+las-1)%mod1+1;
			y_1=(y_1+las-1)%mod2+1;
			if(x_0>x_1)swap(x_0,x_1),swap(y_0,y_1);//发现反了要换回来 
			if(x_0==x_1)a[++tot]={0,max(y_0,y_1)*1.0};
			else a[++tot].k=1.0*(y_1-y_0)/(x_1-x_0),a[tot].b=y_0-x_0*a[tot].k;//求斜率和截距 
			modify(rt,1,mod1,x_0,x_1,tot);//修改 
		}
	}
	return 0;
}