初见安~这里是咕咕咕的樱狸~
啊李超线段树其实挺简单的【bushi】，就不分点了直接开讲吧。
首先李超线段树是处理这种问题的：
给定平面直角坐标系和若干线段【假设均在第一象限】，求与某条x=a线段的交点纵坐标的最大值。
即：
我们要求的就是y。
显然如果每次询问都过一次所有线段，复杂度就是
的。所以利用到区间的思想，我们可以用到线段树维护各个区间的线段，并且保证线段树上的各个区间的线段都能完全覆盖该区间，然后进行单点查询。那么每个区间就会有多条线段，其中会有可以舍去的，比如：
蓝色区间内，下面的两条线段是可以扔掉的。所以我们要做的就是每个区间只维护一条线段，才能保证复杂度。
如果出现的是上图中一条线段被另一条线段完全覆盖的情况，我们可以直接取舍。那如果是相交的呢？
如图，红绿两线相交，如果要单点查询的话交点右侧取红色线段，同理左侧。这时候我们就可以把其中一条线段down下去——放到子区间去。
比如交点在mid左侧，那么我们就把红色线段下传到l~mid这个子区间去，因为显然红色线段在l~mid这个区间里有可能提供最大值；并将绿色线段保留在l~r区间。
也就是说，为了取得某单点的最大值，我们需要完整遍历这log层的线段取max，每个区间一条线段，就保证了复杂度是
了。
也很好实现，就像一个普通的线段树。看一个例题：洛谷P4254 [JSOI2008]Blue Mary开公司
题解
这就是一个李超树的模板题了。每次给你一条跨越整个区间的线段，询问单点最大值。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define maxn 50004
using namespace std;
typedef long double ld;
int read() {
int x = 0, f = 1, ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
return x * f;
}
int T, n = 50000;
char s[maxn];
struct node {bool flag; ld k, b;} t[maxn << 2];
void add(int p, int l, int r, ld k, ld b) {//y=kx+b
if(!t[p].flag) {t[p].flag = true, t[p].k = k, t[p].b = b; return;}//有没有线段
register int mid = l + r >> 1;
ld l1 = l * k + b, r1 = r * k + b;//在两端点的取值判断覆盖关系
ld l2 = l * t[p].k + t[p].b, r2 = r * t[p].k + t[p].b;
if(l1 <= l2 && r1 <= r2) return;//被完全覆盖
if(l1 > l2 && r1 > r2) {t[p].k = k, t[p].b = b; return;}//完全覆盖
ld x = (b - t[p].b) / (t[p].k - k);//相交
if(l1 > l2) {//判断哪条先在上
if(x <= mid) add(p << 1, l, mid, k, b);//判断交点，down哪个区间
else add(p << 1 | 1, mid + 1, r, t[p].k, t[p].b), t[p].k = k, t[p].b = b;
}
else {//同理分情况
if(x <= mid) add(p << 1, l, mid, t[p].k, t[p].b), t[p].k = k, t[p].b = b;
else add(p << 1 | 1, mid + 1, r, k, b);
}
}
ld ask(int p, int l, int r, int a) {//查询就很简单了 直接看吧
if(l == r) return t[p].k * a + t[p].b;
register int mid = l + r >> 1; ld x = t[p].k * a + t[p].b;
if(a <= mid) x = max(x, ask(p << 1, l, mid, a));
else x = max(x, ask(p << 1 | 1, mid + 1, r, a));
return x;
}
signed main() {
T = read();
while(T--) {
scanf("%s", s);
if(s[0] == 'P') {
ld k, b;
scanf("%Lf %Lf", &b, &k);
add(1, 1, n, k, b - k);
}
else {
register int x = read();
ld ans = ask(1, 1, n, x);
printf("%lld\n", (long long)(ans / 100));
}
}
return 0;
}
有一个比较好的练习题……可惜我自己一直只写了一半卡在那里QvQ后面会写的吧。
洛谷P4069 [SDOI2016] 游戏