「李超线段树」学习笔记

刚接触李超线段树不久，感觉还是很容易掌握的，写一篇简单的博客记录一下
李超线段树解决的是这样一类问题：给定二维平面上的一些线段，求 $x = p o s$ 与这些线段的交点最高的那个点，例如下面这个图，给定 $p o s = 4$ ，则答案就是那个虚线与红线的交点

顾名思义，李超线段树首先是棵线段树，其核心是维护每个区间的“最优势线段”，即在每个区间的中点处最高的线段。

为了更好理解李超线段树，先介绍查询步骤更好一点

查询步骤
设查询的位置为 $p o s$ ，对于线段树上的每一个包含 $p o s$ 的区间，取所有这些区间记录的最优势线段的对应 $x = p o s$ 下的最高点
插入线段步骤
设待插入的线段左端点 $L$ ，右端点 $R$ ，其函数表达式为 $f (x)$ ，对于线段树上的每一个完全被包含在区间 $[L, R]$ 内的区间，更新该区间的“最优势线段”，分类讨论如下

若该区间还没有记录最优势线段，则记录最优势线段并返回
设该区间记录的最优势线段函数表达式为 $f_1(x)$ ，若 $f(L)>f_1(L)$ 且 $f(R)>f_1(R)$ ，则更换最优势线段为 $f_1(x)$ ，并返回
若是两线段交叉的情况，另 $mid=\frac{(L+R)}{2}$ ，若 $f(mid)>f_1(mid)$ ，则交换 $f (x)$ 与 $f_1(x)$ ，由于交换后必有 $f_1(mid)\geq f(mid)$ ，继续讨论 $f (x)$ 与 $f_1(x)$ 的交点横坐标 $x$ 情况
- $x > m i d$
  这时用劣势线段 $（$ 也就是线段 $f (x) ）$ 去继续更新右区间，注意此时的 $f (x)$ 可能是交换后的【如果不是交换后的那么显然要去更新右区间】，其实这并不影响，因为如果是交换后的，那么上一次插入交换前的那个线段的时候，更新完当前区间就返回了，并没有更新右区间，而当交换后，如果不用劣势线段去跟新右区间，将丢失劣势线段的信息，而对于区间 $[x, R]$ 内的点来说，这条劣势线段才是取的最高的那条，所以必须用劣势线段去更新右区间
1. $x < m i d$
  同上分析可知需要用劣势线段去更新左区间
2. $x = m i d$
  当前区间最优势线段可以不更新【因为中点函数值都一样】，但是得更新左区间或者右区间，具体更新哪一个区间根据插入的线段在哪边更高就更新哪边

模板

struct line{
	double k,b;
	int l,r,flag;  //l,r表示线段的左端点和右端点，而线段树的左端点和右端点是不显示存储的
	line(double a=0,double c=0,int d=0,int e=0,int f=0){
		k=a;b=c;l=d;r=e;flag=f;
	}
}seg[maxn<<2];

struct segment_tree{
	inline double calc(line l1,int pos) {return l1.k*pos+l1.b;}  //kx+b
	inline int cross(line l1,line l2) {return floor((l1.b-l2.b)/(l2.k-l1.k));}  //l1 l2交点

	void build(int le,int ri,int id){ 
		seg[id].l=1;seg[id].r=50000;seg[id].flag=0;
		if(le==ri) return;
		int mid=(le+ri)>>1;
		build(le,mid,id<<1);build(mid+1,ri,id<<1|1);
	}

	void insert(int le,int ri,int id,line ins){  //le,ri为需要维护的区间,id为线段树区间编号,ins为需要插入的线段
		if(ins.l<=le&&ins.r>=ri){
			if(!seg[id].flag) {seg[id]=ins;seg[id].flag=1;}
			else if((calc(ins,le)-calc(seg[id],le))>eps&&(calc(ins,ri)-calc(seg[id],ri))>eps) {seg[id]=ins;}
			else if((calc(ins,le)-calc(seg[id],le))>eps||(calc(ins,ri)-calc(seg[id],ri))>eps){
				int mid=(le+ri)>>1;
				if(calc(ins,mid)-calc(seg[id],mid)>eps) swap(seg[id],ins);
				if(cross(seg[id],ins)-mid<-eps) insert(le,mid,id<<1,ins);
				else if(cross(seg[id],ins)-mid>eps) insert(mid+1,ri,id<<1|1,ins);
				else{
					if(calc(seg[id],le)<calc(ins,le)) insert(le,mid,id<<1,ins);
					else insert(mid+1,ri,id<<1|1,ins); 
				}
			}
		}else{
			int mid=(le+ri)>>1;
			if(ins.l<=mid) insert(le,mid,id<<1,ins);
			if(ins.r>mid) insert(mid+1,ri,id<<1|1,ins);
		}
	}

	double query(int le,int ri,int id,int pos){ //le,ri表示当前询问的区间,如果x=pos处没有对应的线段，会返回-inf
		if(le==ri) return seg[id].flag?calc(seg[id],pos):-inf;
		int mid=(le+ri)>>1;double res=seg[id].flag?calc(seg[id],pos):-inf;
		if(pos<=mid) res=max(res,query(le,mid,id<<1,pos));
		else res=max(res,query(mid+1,ri,id<<1|1,pos));
		return res;
	}
}tree;

1568: [JSOI2008]Blue Mary开公司

Time Limit: 15 Sec Memory Limit: 162 MBSubmit: 2583 Solved: 965

Description

在这里插入图片描述

Input

第一行：一个整数 $N$ ，表示方案和询问的总数。
接下来 $N$ 行，每行开头一个单词“ $Q u e r y$ ”或“ $P r o j e c t$ ”。
若单词为 $Q u e r y$ ，则后接一个整数T，表示 $B l u e M a r y$ 询问第 $T$ 天的最大收益。
若单词为 $P r o j e c t$ ，则后接两个实数 $S ， P$ ，表示该种设计方案第一天的收益 $S$ ，以及以后每天比上一天多出的收益 $P$ 。
$1 <= N <= 100000 1 <= T <=50000 0 < P < 100，| S | <= 10^6$
提示：本题读写数据量可能相当巨大，请选手注意选择高效的文件读写方式。

Output

对于每一个 $Q u e r y$ ，输出一个整数，表示询问的答案，并精确到整百元（以百元为单位，
例如：该天最大收益为 $210$ 或 $290$ 时，均应该输出 $2$ ）。没有方案时回答询问要输出 $0$

Sample Input

10
Project 5.10200 0.65000
Project 2.76200 1.43000
Query 4
Query 2
Project 3.80200 1.17000
Query 2
Query 3
Query 1
Project 4.58200 0.91000
Project 5.36200 0.39000

Sample Output

题解

每一个方案随时间的变化规律都可以表示成一个直线方程，然后就是模版题了
注意描述中“一开始没有收到任何方案时，你可以认为每天的最大收益值是 $0$ ”这句话还是有点歧义的，并不是说没有插入任何线段之前查询的话输出 $0$ ，插入之后在所有方案中查询一个最高点。而是任何时间查询都可以是 $0$ ，也就是可以不选择任何方案，所以就直接插入一个 $k = 0 ， b = 0$ 的线段就行了

代码

#include<bits/stdc++.h>

using namespace std;
const int maxn=1e5+10;
#define eps 1e-9
#define inf 0x3f3f3f3f

struct line{
	double k,b;
	int l,r,flag;  //l,r表示线段的左端点和右端点，而线段树的左端点和右端点是不显示存储的
	line(double a=0,double c=0,int d=0,int e=0,int f=0){
		k=a;b=c;l=d;r=e;flag=f;
	}
}seg[maxn<<2];

struct segment_tree{
	inline double calc(line l1,int pos) {return l1.k*pos+l1.b;}  //kx+b
	inline int cross(line l1,line l2) {return floor((l1.b-l2.b)/(l2.k-l1.k));}  //l1 l2交点

	void build(int le,int ri,int id){   //这个操作好像没啥用233
		seg[id].l=1;seg[id].r=50000;seg[id].flag=0;
		if(le==ri) return;
		int mid=(le+ri)>>1;
		build(le,mid,id<<1);build(mid+1,ri,id<<1|1);
	}

	void insert(int le,int ri,int id,line ins){  //le,ri为需要维护的区间,id为线段树区间编号,ins为需要插入的线段
		if(ins.l<=le&&ins.r>=ri){
			if(!seg[id].flag) {seg[id]=ins;seg[id].flag=1;}
			else if((calc(ins,le)-calc(seg[id],le))>eps&&(calc(ins,ri)-calc(seg[id],ri))>eps) {seg[id]=ins;}
			else if((calc(ins,le)-calc(seg[id],le))>eps||(calc(ins,ri)-calc(seg[id],ri))>eps){
				int mid=(le+ri)>>1;
				if(calc(ins,mid)-calc(seg[id],mid)>eps) swap(seg[id],ins);
				if(cross(seg[id],ins)-mid<-eps) insert(le,mid,id<<1,ins);
				else if(cross(seg[id],ins)-mid>eps) insert(mid+1,ri,id<<1|1,ins);
				else{
					if(calc(seg[id],le)<calc(ins,le)) insert(le,mid,id<<1,ins);
					else insert(mid+1,ri,id<<1|1,ins); 
				}
			}
		}else{
			int mid=(le+ri)>>1;
			if(ins.l<=mid) insert(le,mid,id<<1,ins);
			if(ins.r>mid) insert(mid+1,ri,id<<1|1,ins);
		}
	}

	double query(int le,int ri,int id,int pos){ //le,ri表示当前询问的区间
		if(le==ri) return seg[id].flag?calc(seg[id],pos):-inf;
		int mid=(le+ri)>>1;double res=seg[id].flag?calc(seg[id],pos):-inf;
		if(pos<=mid) res=max(res,query(le,mid,id<<1,pos));
		else res=max(res,query(mid+1,ri,id<<1|1,pos));
		return res;
	}
}tree;

int n,pos,l,r;
char opt[100];
double k,b;

int main()
{
	scanf("%d",&n);tree.insert(1,50000,1,line(0,0,1,50000,1));
	while(n--){
		scanf("%s",opt+1);
		if(opt[1]=='P'){
			scanf("%lf %lf",&b,&k);
			tree.insert(1,50000,1,line(k,b-k,1,50000,1));
		}else{
			scanf("%d",&pos);double res=tree.query(1,50000,1,pos);
			printf("%d\n",(int)floor(res/100));
		}
	}
}

3938: Robot

Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 493 Solved: 162

Description

小 $q$ 有 $n$ 只机器人，一开始他把机器人放在了一条数轴上，第 $i$ 只机器人在ai的位置上静止，而自己站在原点。在这
之后小 $q$ 会执行一些操作，他想要命令一个机器人向左或者向右移动 $x$ 格。但是机器人似乎听不清小 $q$ 的命令，事实
上它们会以每秒 $x$ 格的速度匀速移动。看着自己的机器人越走越远，小 $q$ 很着急，他想知道当前离他（原点）最远的
机器人有多远。具体的操作以及询问见输入格式。注意，不同的机器人之间互不影响，即不用考虑两个机器人撞在
了一起的情况。

Input

共有 $m$ 个事件，输入将会按事件的时间顺序给出。第一行两个正整数 $n, m$ 。接下来一行 $n$ 个整数，第 $i$ 个数是 $a_i$ ，表示
第 $i$ 个机器人初始的位置（初始移动速度为 $0$ ）。接下来 $m$ 行，每行行首是一个非负整数 $t_i$ ，表示该事件点发生的时
刻（以秒为单位）。第二个是一个字符串 $S$ ，代表操作的种类。数字与字符串之间用一个空格隔开。接下来的输入
按 $S$ 的种类分类。若 $S$ 是“ $c o m m a n d$ ”（不带引号），则接下来两个整数 $k_i,x_i$ ，表示小 $q$ 对第 $k_i$ 个机器人执行了操作
，该机器人的速度将会被重置，变为向数轴正方向每秒移动 $x_i$ 格（若 $x_i$ 为负数就相当于向数轴负方向每秒移动 $x_i ∣$ 格）。保证 $1\leq k_i\leq n$ 。若 $S$ 是“ $q u e r y$ ”（不带引号），则你需要输出当前离原点最远的机器人有多远。保证 $t_1 \leq t_2 \leq t_2 \leq...\leq tm$ 。（注：若同一时间发生多次操作，则按读入顺序依次执行）

Output

对于每个 $q u e r y$ 询问，输出一行，包含一个整数表示正确的答案。 $C / C + +$ 输入输出 $long\ long$ 时请用 $\%lld$ 。由于本题数
据量较大，建议不要使用 $c i n / c o u t$ 进行输入输出。

Sample Input

4 5
-20 0 20 100
10 command 1 10
20 command 3 -10
30 query
40 command 1 -30
50 query

Sample Output

180
280

HINT

第一个命令执行时，各个机器人的位置为： $- 20, 0, 20, 100$ 。
第二个命令执行时，各个机器人的位置为： $80, 0, 20, 100$ 。
第一个询问时，各个机器人的位置为： $180, 0, - 80, 100$ 。
第三个命令执行时，各个机器人的位置为： $280, 0, - 180, 100$ 。
第二个询问时，各个机器人的位置为： $- 20, 0, - 280, 100$ 。

限制与约定

设 $c o m m a n d$ 的个数为 $C$ ， $q u e r y$ 的个数为 $Q$ 。（所以 $C + Q = m$ ）
对于所有的事件满足 $\leq ti \leq 10^9$ ，对于所有的 $c o m m a n d$ 满足 $∣x_i∣\leq 10^4$ 。
对于所有的机器人满足 $∣ai∣\leq 10^9$ 。
$\leq 10^5$
$\leq 5*10^5$

Source

2015年集训队互测 By zhj

题意：

就是n个机器人在x轴上，给你所有机器人初始(0时刻)位置静止，然后给定两种操作，一个是让某个机器人以一定的速度开始运动，另一个操作是查询某个时刻距离原点最远的机器人的距离

题解

网上很多大神都是写的李超线段树+离散化，个人更喜欢动态开点
很容易看出来位置-时间是一个一次函数，所以就转化为李超线段树解决，首先需要明确的是后面的修改不会对前面的查询造成影响，因为 $t_1\leq t_2\leq... \leq t_m$ 。所以考虑离线处理，即将所有线段插入到线段树中，然后再一起查询所有答案，注意有一个小的 $t r i k$ 就是同一个时间对同一个点可能修改很多次，这时要注意保留最后一次修改的那个，这个 $d e b u g$ 数据我放在了代码后面，然后还有一个小技巧就是不用去维护最低的点，每次插入的时候同时插入一条关于 $x$ 轴对称的线段就行了，这样就只用维护最大值了，分析一下时间复杂度，首先查询是 $O(log 10^9)$ ，修改过程也是 $O(log 10^9)$ ，总时间复杂度 $O(m log 10^9)$ ，空间复杂度 $O(mlog 10^9)$

同时

g e t

到一个新操作

vector::insert()
iterator insert ( iterator position, const T& x );
void insert ( iterator position, size_type n, const T& x );

template <class InputIterator>
void insert ( iterator position, InputIterator first, InputIterator last );

插入新的元素，

第一个函数，在迭代器指定的位置前插入值为x的元素

第二个函数，在迭代器指定的位置前插入n个值为x的元素

第三个函数，在迭代器指定的位置前插入另外一个容器的一段序列迭代器first到last

若插入新的元素后总得元素个数大于capacity，则又一次分配空间

代码

#include<bits/stdc++.h>

using namespace std;
const int maxn=2e5+10;
#define eps 1e-9
#define inf 2e18
#define L 0
#define R 1e9

struct line{
	long long k,b;
	int l,r,flag,ls,rs;  //l,r表示线段的左端点和右端点，而线段树的左端点和右端点是不显示存储的,ls左儿子，rs右儿子
	line(long long a=0,long long c=0,int d=0,int e=0,int f=0,int g=0,int h=0){
		k=a;b=c;l=d;r=e;flag=f;ls=g;rs=h;
	}
}seg[maxn*30];

struct segment_tree{
	int tot;
	segment_tree() {tot=1;}
	inline long long calc(line l1,int pos) {return l1.k*pos+l1.b;}  //kx+b
	inline long long cross(line l1,line l2) {return (long long)((l1.b-l2.b)/(l2.k-l1.k));}  //l1 l2交点

	void insert(int le,int ri,int id,line ins){  //le,ri为需要维护的区间,id为线段树区间编号,ins为需要插入的线段
		if(ins.l>ins.r) return;
		if(ins.l<=le&&ins.r>=ri){
			if(!seg[id].flag) {
				swap(seg[id],ins);seg[id].ls=ins.ls;seg[id].rs=ins.rs;
			}
			else if((calc(ins,le)-calc(seg[id],le))>eps&&(calc(ins,ri)-calc(seg[id],ri))>eps) {
				swap(seg[id],ins);seg[id].ls=ins.ls;seg[id].rs=ins.rs;
			}
			else if((calc(ins,le)-calc(seg[id],le))>eps||(calc(ins,ri)-calc(seg[id],ri))>eps){
				int mid=(le+ri)>>1;
				if(calc(ins,mid)-calc(seg[id],mid)>eps) {
					swap(seg[id],ins);seg[id].ls=ins.ls;seg[id].rs=ins.rs;
				}
				if(cross(seg[id],ins)-mid<-eps) {
					if(!seg[id].ls) seg[id].ls=++tot;
					insert(le,mid,seg[id].ls,ins);
				}
				else if(cross(seg[id],ins)-mid>eps) {
					if(!seg[id].rs) seg[id].rs=++tot;
					insert(mid+1,ri,seg[id].rs,ins);
				}
				else{
					if(calc(seg[id],le)<calc(ins,le)) {
						if(!seg[id].ls) seg[id].ls=++tot;
						insert(le,mid,seg[id].ls,ins);
					}
					else {
						if(!seg[id].rs) seg[id].rs=++tot;
						insert(mid+1,ri,seg[id].rs,ins); 
					}
				}
			}
		}else{
			int mid=(le+ri)>>1;
			if(ins.l<=mid) {
				if(!seg[id].ls) seg[id].ls=++tot;
				insert(le,mid,seg[id].ls,ins);
			}
			if(ins.r>mid) {
				if(!seg[id].rs) seg[id].rs=++tot;
				insert(mid+1,ri,seg[id].rs,ins);
			}
		}
	}

	long long query(int le,int ri,int id,int pos){ //le,ri表示当前询问的区间
		if(le==ri) return calc(seg[id],pos);
		int mid=(le+ri)>>1;long long res=calc(seg[id],pos);
		if(pos<=mid&&seg[id].ls)  res=max(res,query(le,mid,seg[id].ls,pos));
		else if(pos>mid&&seg[id].rs) res=max(res,query(mid+1,ri,seg[id].rs,pos));
		return res;
	}
}tree;

char opt[100];
vector<pair<int,long long> > pos[maxn];
int a[maxn],n,m,x,t,que[3*maxn],cnt=0;long long k;


int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++){
		scanf("%d %s",&t,opt+1);
		if(opt[1]=='q') que[++cnt]=t;
		else{
			scanf("%d %lld",&x,&k);
			pos[x].push_back(make_pair(t,k));
		}
	}
	for(int i=1;i<=n;i++) pos[i].insert(pos[i].begin(),make_pair(0,0)),pos[i].insert(pos[i].end(),make_pair(1e9+1,0));
	for(int i=1;i<=n;i++){
		long long last=a[i];
		for(int j=0;j<pos[i].size()-1;j++){
			long long b=last-pos[i][j].first*pos[i][j].second,k=pos[i][j].second;
			tree.insert(L,R,1,line(pos[i][j].second,b,pos[i][j].first,pos[i][j+1].first-1,1));
			tree.insert(L,R,1,line(-pos[i][j].second,-b,pos[i][j].first,pos[i][j+1].first-1,1));
			last=pos[i][j].second*pos[i][j+1].first+b;
		}
	}
	for(int i=1;i<=cnt;i++) printf("%lld\n",tree.query(L,R,1,que[i]));
}

/* 答案48
1 3
0
0 command 1 -3
0 command 1 -6
8 query
*/

原文链接：https://blog.csdn.net/qq_40791842/article/details/92263958

查询步骤

插入线段步骤

模板

1568: [JSOI2008]Blue Mary开公司

Description

Input

Output

Sample Input

Sample Output

题解

代码

3938: Robot

Description

Input

Output

Sample Input

Sample Output

HINT

限制与约定

Source

题意：

题解

代码