初見安~這裡是咕咕咕的櫻狸~
啊李超線段樹其實挺簡單的【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] 遊戲