【学习笔记】李超树

李超树,一种奇怪的数据结构——然而其实是线段树,用于维护平面优势直线。

顺便学了学标记永久化。

虽然不知道是谁,但是先orz李超233

$1$ 标记永久化

似乎李超树不是很好 push_down 的样子,于是去网上学了一发。大概思想就是,线段树区间维护时信息不再打标记,而是选择把标记打在自己身上不再下传。查询的时候一路查下去,记录覆盖在这条路径上的信息,然后基于修改的信息对整个区间的信息合并一下即可。

然后是瞎写的伪代码?Sumblime 3 真好用,自创语法真有趣233

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
//默认区间修改 = 区间的每个单点更新信息 
Class Segment_Tree{
Inform * Tag, Val ;
int : L, R, Mid, Lson, Rson ;
Function Clear() {....} ;
}//其中 *Tag 是当前点维护信息时打的标记,*Val 是当前节点的信息。

Function[Inform] Merge(Inform * n, Inform * m) {....} ;
Function[void] Update(Segment_Tree *T, int root, int qL, int qR, Inform *S){
Do_Some_Work(T[root], qL, qR, S) ;
if (T[root] -> L >= qL && T[root] -> R <= qR)
return T[root].Tag = Merge(S, T[root].tag), void() ;
if (qL <= T[root] -> Mid)
Update(T, T[root].Lson, qL, qR, S) ;
if (qR > T[root] -> Mid)
Update(T, T[root].Rson, qL, qR, S) ;
return void() ;
}
Function[Inform] Query(Segment_Tree *T, int root, int qL, int qR, Inform *S){
//询问操作,最后一个参数代表一路询问下来的合并标记
Inform * res ; res = EMPTY ;
if (T[root] -> L >= qL && T[root] -> R <= qR)
return res = Merge(T[root].Val, S) ;
if (qL <= T[root] -> Mid)
res = Merge(res, Query(T, T[root].Lson, qL, qR, Merge(S, T[root].tag))) ;
if (qR > T[root] -> Mid)
res = Merge(res, Query(T, T[root].Rson, qL, qR, Merge(S, T[root].tag))) ;
return res ;
}

$2$ 李超树

首先李超树的最简单操作就是:

  • 向平面内添加一条直线
  • 查询覆盖在某个坐标上的直线中,纵坐标值最大/最小值
  • $n,m\leq 200,000$

考虑如何维护这个东西,考虑维护每个点代表区间的优势直线,即在大多数区域内可能是最优解的那条线——或者,在代表区间的中点是最优解的直线。这么做采用了启发式的思想,保存了有限多的备选最优解。于是就可以保证最后询问的时候,采用标记永久化的思想,取所有覆盖在一个单点上的优势直线的最大值即可,复杂度 $\log n$ 。

那么考虑怎么维护优势区间。假设区间 $\rm [L,R]$ 的优势直线为 $l$ ,现在插入一条直线 $l’$,开始分类讨论:

  • 如果当前区间的左端和右端都满足 $l’$ 更优,那么直接拿 $l’$ 替代。
  • 如果当前取件的左端和右端都满足 $l’$ 更劣,那么 $l’$ 爱滚哪去滚哪去。

  • $\mathrm {slope}(l’)>\mathrm{slope}(l)$

    • 当 $l$ 在中点处的值比 $l’$ 劣时,那么左区间可能要算一波,右区间就一定会是 $l’$ 更优。这个时候为了保证 $l$ 作为潜在的优选方案不丢失,就把 $l’$ 保存在当前区间,把 $l$ 送到自己的左儿子区间。

    • $l’$ 更劣时,那么右区间可能算一波,当前区间的优势直线也不会变,所以只去改右区间即可。

  • $\mathrm {slope}(l’)<\mathrm{slope}(l)$

    • 同理可证,显然,证毕(

于是就上代码,模板题 LG4254 JSOI2008 BlueMarry开公司。注意本题给的直线需要平移一下再用。

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
double b[N << 2], k[N << 2] ;
char s[N] ; int m, n, v[N << 2], x, cnt ;

il double val(double x, int id){
return k[id] * (x - 1) + b[id] ;
}
void update(int rt, int l, int r, int id){
int mid = (l + r) >> 1 ;
double o, p, q, u, s, t ;
o = val(l, id), p = val(l, v[rt]) ;
q = val(r, id), u = val(r, v[rt]) ;
s = val(mid, id), t = val(mid, v[rt]) ;
if (o <= p && q <= u) return void() ;
if (o > p && q > u) return v[rt] = id, void() ;
if (k[v[rt]] > k[id20])
if (s < t) update(rt << 1, l, mid, id) ;
else update(rt << 1 | 1, mid + 1, r, v[rt]), v[rt] = id ;
else
if (s < t) update(rt << 1 | 1, mid + 1, r, id) ;
else update(rt << 1, l, mid, v[rt]), v[rt] = id ;
}
double query(int rt, int l, int r, int x){
int mid = (l + r) >> 1 ;
if (l == r) return val(x, v[rt]) ;
if (x <= mid)
return max(val(x, v[rt]), query(rt << 1, l, mid, x)) ;
else
return max(val(x, v[rt]), query(rt << 1 | 1, mid + 1, r, x)) ;
}
int main(){
cin >> m, n = 50001 ;
while (m --){
scanf("%s", s + 1) ;
if (s[1] == 'P')
++ cnt,
scanf("%lf%lf", &b[cnt], &k[cnt]),
update(1, 1, n, cnt) ;
else
scanf("%d", &x),
printf("%d\n", (int)query(1, 1, n, x) / 100) ;
}
return 0 ;
}

$3$ 一道例题

例题就是 HEOI2013 Segment 。插入一条线段,维护每个横坐标的优势线段编号。

发现魔改一下就可以。然后一个坑点就是斜率为 $\inf$ 的线段要特殊处理一下,然而一开始自己直接把这种线段的 $\max val$ 当作 $\inf$ 算了也是很降智。

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
#define N 100010
#define il inline
#define Inf 19260817.0

#define M1 39989
#define M2 1000000000

using namespace std ;

double b[N << 2], k[N << 2] ;
int L, m, mk, n, v[N << 2], x, cnt ;

il double val(double x, int id){
return 1.0 * x * k[id] + b[id] ;
}
void update(int rt, int l, int r, int ul, int ur, int id){
int mid = (l + r) >> 1 ;
if (l >= ul && r <= ur){
double o, p, q, u, s, t ;
o = val(l, id), p = val(l, v[rt]) ;
q = val(r, id), u = val(r, v[rt]) ;
s = val(mid, id), t = val(mid, v[rt]) ;
if (o <= p && q <= u) return void() ;
if (o > p && q > u) return v[rt] = id, void() ;
if (k[v[rt]] > k[cnt])
if (s < t) update(rt << 1, l, mid, ul, ur, id) ;
else update(rt << 1 | 1, mid + 1, r, ul, ur, v[rt]), v[rt] = id ;
else
if (s < t) update(rt << 1 | 1, mid + 1, r, ul, ur, id) ;
else update(rt << 1, l, mid, ul, ur, v[rt]), v[rt] = id ;
}
if (ul <= mid) update(rt << 1, l, mid, ul, ur, id) ;
if (ur > mid) update(rt << 1 | 1, mid + 1, r, ul, ur, id) ;
}
int query(int rt, int l, int r, int x){
// cout << l << " " << r << endl ;
int mid = (l + r) >> 1 ;
if (l == r) return v[rt] ;
if (x <= mid){
int id = query(rt << 1, l, mid, x) ;
if (val(x, id) > val(x, v[rt])) return id ; else return v[rt] ;
}
else {
int id = query(rt << 1 | 1, mid + 1, r, x) ;
if (val(x, id) > val(x, v[rt])) return id ; else return v[rt] ;
}
}
int w(int x){ return (x + L - 1) % M1 + 1 ; }
int g(int x){ return (x + L - 1) % M2 + 1 ; }
int main(){
int a, e, c, d ;
cin >> m, n = 50001 ;
while (m --){
scanf("%d", &mk) ;
if (mk){
++ cnt ;
scanf("%d%d%d%d", &a, &e, &c, &d) ;
a = w(a), e = g(e), c = w(c), d = g(d) ;
// cout << a << " " << e << " " << c << " " << d << endl ;
if (a > c) swap(a, c), swap(d, e) ;
if (c == a) k[cnt] = 0, b[cnt] = max(d, e) ;
else k[cnt] = (double)(d - e) / (double)(c - a),
b[cnt] = 1.0 * d - 1.0 * c * k[cnt] ;
// cout << k[cnt] << " " << b[cnt] << endl ;
update(1, 1, n, a, c, cnt) ;
}
else
scanf("%d", &x), x = w(x),
printf("%d\n", L = query(1, 1, n, x)) ;
}
return 0 ;
}