title: "data structure" Li Chao line segment tree
date: 2022-01-22 10:38:01
tags:

• c++
• data structure
  categories:
• data structure
  mathjax: true
  description: a brief explanation of Li Chao's line segment tree

#0.0 chip in front

Li Chao's line segment tree is built by Li Chao, the team master of Xuejun middle school Provincial lectures Proposed in.

In fact, on the whole, there is nothing special, but the information maintained by the segment tree is specialized.

#1.0 general

#1.1 applicable issues

Support the dynamic maintenance of a plane rectangular coordinate system, support the insertion of lines / segments, and query the lines with the maximum / minimum vertical coordinates of the intersection of lines / segments with lines \ (x=x_0 \).

#1.2 general idea

In each interval, the longest straight line that completely passes through the interval and is located at the top layer is maintained, and the idea of mark permanence is used.

Consider inserting a straight line and processing to a certain interval, then there may be the following situations:

• The current section is not covered by any line segment and can be modified directly;
• Judge whether the new line segment is completely covered by the original line segment according to the endpoint value, and return directly;
• Judge whether the new line segment completely covers the original line segment according to the endpoint value, modify it directly, and then return;
• Judge the length relationship through the size relationship between the intersection position and the endpoint value, and recursively enter the long records and short records into the corresponding subtree;

When querying, the idea of marking permanence is to take out and compare each recorded line segment.

To sum up, the query time complexity is \ (O(\log n) \)

In fact, for the line segment to be inserted, we first divide the covered intervals into \ (O(\log n) \) through the line segment tree, and then perform the above operation separately for each fully covered interval. When the above operation is performed separately, the length of each line segment is at least halved, so the \ (O(\log n) \) layer is recursive down at most, so the overall time complexity is modified to \ (O(\log^2n) \)

#2.0 application

#2.1 board

P4254 [JSOI2008]Blue Mary started the company

Since the inserted line is not a line segment, it does not need to be segmented first and can be modified directly.

#define ll long long
#define db double

const int N = 200010;
const int LMT = 50010;
const int INF = 0x3fffffff;

template <typename T> void read(T &x) {
    int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

template <typename T> inline T Max(T x, T y) {return x > y ? x : y;}
template <typename T> inline T Min(T x, T y) {return x < y ? x : y;}

struct Node {int ls, rs, val;};
struct Line {
    double k, b;
    inline Line() {k = b = 0;}
    inline Line(double _k, double _b) {k = _k, b = _b;}
    inline double val(int x) {return k * x + b;}
} s[N];

struct LCTree {
    Node p[N]; int cnt, rt;

    inline LCTree() {cnt = rt = 0;}

    void build(int &k, int l, int r) {
        if (!k) k = ++ cnt; if (l == r) return;
        int mid = l + r >> 1; p[k].val = 0;
        build(p[k].ls, l, mid); build(p[k].rs, mid + 1, r);
    }   

    void insert(int k, int l, int r, int id) {
        if (!p[k].val) {p[k].val = id; return;}
        int mid = l + r >> 1;
        db l2 = s[p[k].val].val(l), r2 = s[p[k].val].val(r);
        db l1 = s[id].val(l), r1 = s[id].val(r);
        if (l1 <= l2 && r1 <= r2) return;
        if (l1 > l2 && r1 > r2) {p[k].val = id; return;}
        db x = (s[id].b - s[p[k].val].b) / (s[p[k].val].k - s[id].k);
        if (l1 > l2) {
            if (x > mid) insert(p[k].rs, mid + 1, r, p[k].val), p[k].val = id;
            else insert(p[k].ls, l, mid, id);
        } else {
            if (x > mid) insert(p[k].rs, mid + 1, r, id);
            else insert(p[k].ls, l, mid, p[k].val), p[k].val = id;
        }
    } 
    
    double query(int k, int l, int r, int x) {
        if (l == r) return s[p[k].val].val(x);
        int mid = l + r >> 1; double res = s[p[k].val].val(x);
        if (x <= mid) return Max(query(p[k].ls, l, mid, x), res);
        else return Max(query(p[k].rs, mid + 1, r, x), res);
    }
} t;

int n, lcnt, T; char op[N];

inline void Main() {
    scanf("%s", op);
    if (op[0] == 'P') {
        double k = 0, b = 0; scanf("%lf%lf", &b, &k);
        s[++ lcnt] = Line(k, b - k); t.insert(t.rt, 1, LMT, lcnt);
    } else {
        int x = 0; read(x);
        printf("%lld\n", (ll)(t.query(t.rt, 1, LMT, x) / 100.0));
    }
}

int main() {t.build(t.rt, 1, LMT); read(T); while (T --) Main(); return 0;}

#2.2 slope optimization

"NOI2007" currency exchange

Let \ (f_i \) represent the maximum amount of money you can have by \ (I \) day, and write a general transfer equation first

Where \ (num_A \) and \ (num_B \) respectively represent the number of \ (A \) gold rolls and the number of \ (B \) gold rolls held, which are determined by \ (J \). Obviously, when buying on the \ (J \) day, the proportion of gold roll you can get is certain, so the larger the money you have on the day of buying, the better, that is \ (f_j \), there should be

Similarly, it can be obtained

So we can write the complete state transition equation

Therefore, we can directly regard a decision as a straight line with a slope of \ (\ frac{f_j\cdot R_j}{R_j\cdot a_j+b_j} \) and a longitudinal intercept of \ (\ frac{f_j}{R_j\cdot a_j+b_j} \). For \ (I \), we require the maximum value of the ordinate of the intersection of all existing decision lines and \ (x=\frac{a_i}{b_i} \). Therefore, it can be maintained directly with Li Chao line segment tree.

Reference articles

• [1] Li Chao line segment tree - konjaku yyb

• [2] Li Chao line segment tree - OI Wiki