李超树

标记永久化:不用向上合并?那么查询的时候肯定就要每次都递归到叶子节点,然后在这个递归的过程中取最优值。

李超树

从我目前接触的题目看来,李超树主要用于维护凸壳。

考虑这么一个问题:

二维平面上有 $n$ 个操作:

  1. 加入一条直线
  2. 给定 $x$ 值,查询所有直线对应 $y$ 的最大值

实际上是在维护若干直线组成的下凸壳。

做法

对 $x$ 坐标轴建立线段树,线段树上的每个节点存储着斜率和截距,表示在当前区间,这条直线的某部分在凸壳上。但由于不确定具体是哪部分,所以我们在查询的时候要查询到叶节点(这也是为什么必须要单点查询),然后在查询的过程中取最值即可。

如何维护

我们发现并不需要区间信息的合并,即不用向上合并。因为查询是个递归到叶子节点,且依次取最值的过程。

那么对于一个区间,考虑新加进来一条直线后如何修改。

首先应按照斜率的大小来分类分讨论。 设 $[L,R]$ 的中点为 $mid$,那么我们还要按照两条直线在 $mid$ 处的函数值来确定到底是更新左边还是右边。 所以共有四种情况,具体可以看下面的代码。

例题

题目链接

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
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
const int maxn = 1e5 + 5;

struct Node {
double k, b;
} seg[maxn << 2];

void build(int l, int r, int rt) {
seg[rt].b = seg[rt].k = 0;
if (l == r) return;
int m = l + r >> 1;
build(l, m, lson);
build(m + 1, r, rson);
}
double val(const Node &t, int x) { return t.k * (x - 1) + t.b; }
void update(int l, int r, int rt, Node x) {
if (l == r) {
if (val(seg[rt], l) < val(x, l)) seg[rt] = x;
return;
}
int m = l + r >> 1;
if (x.k > seg[rt].k) {
if (val(x, m) <= val(seg[rt], m)) {
update(m + 1, r, rson, x);
} else {
update(l, m, lson, seg[rt]);
seg[rt] = x;
}
} else {
if (val(x, m) <= val(seg[rt], m)) {
update(l, m, lson, x);
} else {
update(m + 1, r, rson, seg[rt]);
seg[rt] = x;
}
}
}
double query(int l, int r, int rt, int p) {
if (l == r) return val(seg[rt], l);
int m = l + r >> 1;
double ans = val(seg[rt], p);
if (p <= m)
ans = max(ans, query(l, m, lson, p));
else
ans = max(ans, query(m + 1, r, rson, p));
return ans;
}
int main() {
int n;
scanf("%d", &n);
char op[20];
build(1, maxn, 1);
for (int i = 0; i < n; i++) {
scanf("%s", op);
if (op[0] == 'P') {
double k, b;
scanf("%lf%lf", &b, &k);
update(1, maxn, 1, Node{k, b});
} else {
int x;
scanf("%d", &x);
printf("%d\n", int(query(1, maxn, 1, x)) / 100);
}
}
}