Algorithms-Library/Dynamic Li Chao Tree.cpp at main · Alextz307/Algorithms-Library · GitHub

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
69
70
71
72
73
74
75
/// MIN
struct line {
  int m;
  int64_t b;

  int64_t eval(int x) {
    return (int64_t)m * x + b;
  }
};

struct node {
  line l;
  node* lSon;
  node* rSon;

  node(line _l) : l(_l), lSon(nullptr), rSon(nullptr) {}
};

void minSelf(int64_t &x, const int64_t &y) {
  if (y < x) {
    x = y;
  }
}

void addLine(node* x, int lx, int rx, line l) {
  if (lx == rx) {
    if (l.eval(lx) < x->l.eval(lx)) {
      x->l = l;
    }
    return;
  }
  int mid = (lx + rx) >> 1;

  if (l.m < x->l.m) {
    swap(x->l, l);
  }

  if (l.eval(mid) < x->l.eval(mid)) {
    swap(x->l, l);

    if (x->rSon) {
      addLine(x->rSon, mid + 1, rx, l);
    } else {
      x->rSon = new node(l);
    }
  } else {
    if (x->lSon) {
      addLine(x->lSon, lx, mid, l);
    } else {
      x->lSon = new node(l);
    }
  }
}

int64_t query(node* x, int lx, int rx, int pos) {
  int64_t val = x->l.eval(pos);

  if (lx == rx) {
    return val;
  }

  int mid = (lx + rx) >> 1;

  if (pos <= mid) {
    if (x->lSon) {
      minSelf(val, query(x->lSon, lx, mid, pos));
    }
  } else {
    if (x->rSon) {
      minSelf(val, query(x->rSon, mid + 1, rx, pos));
    }
  }

  return val;
}