题解 省选/NOI− 线段树 李超线段树 基础算法 斜率优化 DP

李超线段树

例题：洛谷P4097

Posted by TH911 on August 20, 2025

例题链接

要求在平面直角坐标系下维护两个操作：

  1. 在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$。

  2. 给定一个数 $k$，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大的线段的编号。

    特别地，如果线段是竖直的，则取最上面的点。线段若不存在，则输出 $0$。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq k, x_0, x_1 \leq 39989$，$1 \leq y_0, y_1 \leq 10^9$。强制在线。

李超线段树

插入线段即插入定义域有限制的一次函数。竖直线段即定义域为 $[x,x]$ 的一次函数 $y=b$。

因此可以考虑线段树维护 $x$ 轴上的区间操作，维护区间最高一次函数。（李超树不能维护线段删除。）

传统线段树无法很好地维护，因此有了李超线段树。

一次函数存储

可以结构体配合重载运算符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

struct node{
	int x,y;
};
struct line{
	double k,b;
	line(){
		
	} 
	line(node a,node b){
		if(a.x==b.x){
			k=0;
			line::b=max(a.y,b.y);
		}else{
			k=1.0*(a.y-b.y)/(a.x-b.x);
			line::b=a.y-k*a.x;
		}
	}
	double operator ()(int x){
		return k*x+b;
	}
}a[N+1];

建树

其实没必要，不存储区间端点则不需要建树。一个点维护的信息仅有 $\textit{id}$，而初始时均为 $0$。

1
2
3
4
5
6
7
8
9
10
11
12
13

struct node{
    int l,r;
    int id;//线段编号 
}t[X<<2|1];
void build(int p,int l,int r){
    t[p]={l,r};
    if(l==r){
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}

精度问题

double 具有浮点误差，需要避免。设 eps 为最小精度，本文取 $10^{-9}$。

重定义小于（leq）、大于（geq）和等于（eq）。

1
2
3
4
5
6
7
8
9

bool leq(double a,double b){
    return a-b<-eps;
}
bool geq(double a,double b){
    return a-b>eps; 
}
bool eq(double a,double b){
    return abs(a-b)<=eps;
}

插入线段

其实类似于扫描线的线段树，节点标记并不会下传。

先考虑找出所有在定义域内的线段树节点区间 $[l,r]$。考虑对于每一个线段树节点，维护节点区间内的最高线段编号 $\textit{id}$，且 $[l,r]$ 是定义域内的极大区间，其父区间并不被定义域包含。（$\textit{id}$ 并不会下传）

设插入线段编号为 $x$，和 $x$ 定义域内区间节点 $[l,r]$。所有的 $[l,r]$ 都可以在线段树上 $\mathcal O(\log n)$ 找出来。

找到区间后，考虑更新 $\textit{id}$。

  • 如果 $[l,r]$ 内 $\textit{id}=0$，即不存在，自然最好，可以直接 $\textit{id}\leftarrow x$。

  • 否则 $\textit{id}$ 已经存在，则需要讨论。

    记 $\textit{mid}=\left\lfloor\dfrac{l+r}2\right\rfloor$。

    取 $\textit{id},x$ 在区间中点 $x=\textit{mid}$ 处的取值 $y_{\textit{id}},y_x$。

    • 若 $y_x>y_{\textit{id}}$，则说明 $x$ 一定更优，因此可以 $x\longleftrightarrow\textit{id}$，即交换 $x,\textit{id}$ 的取值。

    • 有：

      1. 若在 $l$ 处有 $\textit{y}_x>\textit{id}$，说明 $x,\textit{id}$ 在 $[l,\textit{mid}]$ 中相交，递归判断左子区间。
      2. 若在 $r$ 处有 $y_x>\textit{id}$，说明 $x,\textit{id}$ 在 $[\textit{mid}+1,r]$ 中相交，递归判断右子区间。

      这二者显然至多一个成立，因此复杂度 $\mathcal O(\log n)$。

时间复杂度：$\mathcal O\left(\log^2n\right)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

bool check(int u,int v,int x){
    double yU=a[u](x),yV=a[v](x);
    return geq(yU,yV)||eq(yU,yV)&&u<v;
}
void down(int p,int x){
    int &id=t[p].id;
    if(t[p].l==t[p].r){
        if(check(x,id,t[p].l)){
            id=x;
        }
        return;
    }
    if(check(x,id,t[p<<1].r)){
        swap(x,id);
    }
    if(check(x,id,t[p<<1].l)){
        down(p<<1,x);
    }
    if(check(x,id,t[p<<1|1].r)){
        down(p<<1|1,x);
    }
}
void update(int p,int l,int r,int x){
    if(l<=t[p].l&&t[p].r<=r){
        down(p,x);
        return;
    }
    if(l<=t[p<<1].r){
        update(p<<1,l,r,x);
    }
    if(t[p<<1|1].l<=r){
        update(p<<1|1,l,r,x);
    }
}

查询线段

单点查询，查询路径上所有的 $\textit{id}$ 中最优的一个即可。

时间复杂度：$\mathcal O(\log n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void chkmax(int &u,int v,int x){
    double yU=a[u](x),yV=a[v](x);
    if(yV>yU){
        u=v;
    }else if(eq(yU,yV)&&v<u){
        u=v;
    }
}
int query(int p,int x){
    int ans=t[p].id;
    if(t[p].l==t[p].r){
        return ans;
    }
    if(x<=t[p<<1].r){
        chkmax(ans,query(p<<1,x),x);
    }else{
        chkmax(ans,query(p<<1|1,x),x);
    }
    return ans;
}

例题 AC 代码

注意强制在线的写法，不要模数取错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e5,X=39989,Y=1e9;
constexpr const double eps=1e-9;
struct node{
	int x,y;
};
struct line{
	double k,b;
	line(){
		
	} 
	line(node a,node b){
		if(a.x==b.x){
			k=0;
			line::b=max(a.y,b.y);
		}else{
			k=1.0*(a.y-b.y)/(a.x-b.x);
			line::b=a.y-k*a.x;
		}
	}
	double operator ()(int x){
		return k*x+b;
	}
}a[N+1];
struct LiChaoSegTree{
	struct node{
		int l,r;
		int id;//线段编号 
	}t[X<<2|1];
	void build(int p,int l,int r){
		t[p]={l,r};
		if(l==r){
			return;
		}
		int mid=l+r>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
	}
	bool leq(double a,double b){
		return a-b<-eps;
	}
	bool geq(double a,double b){
		return a-b>eps; 
	}
	bool eq(double a,double b){
		return abs(a-b)<=eps;
	}
	bool check(int u,int v,int x){
		double yU=a[u](x),yV=a[v](x);
		return geq(yU,yV)||eq(yU,yV)&&u<v;
	}
	void down(int p,int x){
		int &id=t[p].id;
		if(t[p].l==t[p].r){
			if(check(x,id,t[p].l)){
				id=x;
			}
			return;
		}
		if(check(x,id,t[p<<1].r)){
			swap(x,id);
		}
		if(check(x,id,t[p<<1].l)){
			down(p<<1,x);
		}
		if(check(x,id,t[p<<1|1].r)){
			down(p<<1|1,x);
		}
	}
	void update(int p,int l,int r,int x){
		if(l<=t[p].l&&t[p].r<=r){
			down(p,x);
			return;
		}
		if(l<=t[p<<1].r){
			update(p<<1,l,r,x);
		}
		if(t[p<<1|1].l<=r){
			update(p<<1|1,l,r,x);
		}
	}
	void chkmax(int &u,int v,int x){
		double yU=a[u](x),yV=a[v](x);
		if(yV>yU){
			u=v;
		}else if(eq(yU,yV)&&v<u){
			u=v;
		}
	}
	int query(int p,int x){
		int ans=t[p].id;
		if(t[p].l==t[p].r){
			return ans;
		}
		if(x<=t[p<<1].r){
			chkmax(ans,query(p<<1,x),x);
		}else{
			chkmax(ans,query(p<<1|1,x),x);
		}
		return ans;
	}
}t;
int main(){
	/*freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);*/
	
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n;
	cin>>n;
	t.build(1,1,X);
	int lastans=0;
	for(int i=1,id=0;i<=n;i++){
		int op,k;
		node a,b;
		cin>>op;
		switch(op){
			case 0:
				cin>>k;
				k=(k+lastans-1)%X+1;
				lastans=t.query(1,k);
				cout<<lastans<<'\n';
				break;
			case 1:
				cin>>a.x>>a.y>>b.x>>b.y;
				a.x=(a.x+lastans-1)%X+1;
				a.y=(a.y+lastans-1)%Y+1;
				b.x=(b.x+lastans-1)%X+1;
				b.y=(b.y+lastans-1)%Y+1;
				if(a.x>b.x){
					swap(a,b);
				}
				id++;
				::a[id]=line(a,b);
				t.update(1,a.x,b.x,id);
				break;
		}
	}
	
	cout.flush();
	
	/*fclose(stdin);
	fclose(stdout);*/
	return 0;
}

李超线段树维护斜率优化 DP

李超线段树同样可以用于维护斜率优化 DP，并且可以处理决策点不单调的情况。

参见此处。

CATALOG
    FEATURED TAGS
    树状数组 题解 提高+/省选− 省选/NOI− DP 普及+/提高 基础算法 数学 组合数学 普及/提高− 贪心 字符串 线段树 未完 图论 平衡树 数论 树形 DP 搜索 Tarjan Trie 二分 位运算 二分答案 状态压缩 FHQ Treap 前端 无聊时候的一点思考 最短路 树链剖分 NOI/NOI+/CTSC
    FRIENDS