总结-李超线段树

概念

李超线段树可用来维护直线关系，支持：
1* 加入一条直线
2* 询问单点对应最优直线
结构与普通线段树类似，但更多分情况讨论

LuoguP4254 [JSOI2008]Blue Mary开公司

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long

#define ON_DEBUGG

#ifdef ON_DEBUGG

#define D_e_Line printf("\n----------\n")
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC)

#else

#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)

#endif

using namespace std;
struct ios{
    template<typename ATP>inline ios& operator >> (ATP &x){
        x = 0; int f = 1; char ch;
        for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
        while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();
        x *= f;
        return *this;
    }
}io;

template<typename ATP>inline ATP Max(ATP a, ATP b){
    return a > b ? a : b;
}
template<typename ATP>inline ATP Min(ATP a, ATP b){
    return a < b ? a : b;
}
template<typename ATP>inline ATP Abs(ATP a){
    return a < 0 ? -a : a;
}

const int N = 5e5 + 7;
const int M = 5e5 + 3;

int tot;

double K[N << 1], B[N << 1];

int t[N << 2] ;
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
// y = k * x + b

double Calc(int id, int x) {
    return K[id] * (x - 1) + B[id];
}

inline void Updata(int rt, int l, int r, int x) {
    if(l == r){
        if(Calc(x, l) > Calc(t[rt], l)) t[rt] = x;
        return;
    }
    int mid = (l + r) >> 1;
    if(K[t[rt]] < K[x]){
        if(Calc(x, mid) > Calc(t[rt], mid)){
            Updata(lson, t[rt]);
            t[rt] = x;
        }
        else{
            Updata(rson, x);
        }
    }
    if(K[t[rt]] > K[x]){
        if(Calc(x, mid) > Calc(t[rt], mid)){
            Updata(rson, t[rt]);
            t[rt] = x;
        }
        else{
            Updata(lson, x);
        }
    }
}

inline double Query(int rt, int l, int r, int x) {
    if(l == r) return Calc(t[rt], x);
    int mid = (l + r) >> 1;
    if(x <= mid){
        return Max(Calc(t[rt],x), Query(lson, x));
    }
    else{
        return Max(Calc(t[rt], x), Query(rson, x));
    }

}
int main() {
    int n;
    io >> n;
    char opt[13];
    while(n--){
        scanf("%s", opt + 1);
        if(opt[1] == 'P'){
            ++tot;
            scanf("%lf%lf", &B[tot], &K[tot]);
            Updata(1, 1, M, tot);
        }
        else{
            int x;
            io >> x;
            printf("%d\n", (int)Query(1, 1, M, x) / 100);
        }
    }

    return 0;
}