radoslav11

Dynamic Li Chao segment tree

May 25th, 2017
1,052
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5. const int MAXN = (1 << 20);
  6. const int64_t inf = (int64_t)1e17 + 42;
  7.  
  8. struct LiChao_max
  9. {
  10.     struct line
  11.     {
  12.         int a, b;
  13.         line() { a = 0; b = 0; }
  14.         line(int _a, int _b) { a = _a; b = _b; }
  15.         int64_t eval(int x) { return a * 1ll * x + (int64_t)b; }
  16.     };
  17.  
  18.     struct node
  19.     {
  20.         node *l, *r; line f;
  21.  
  22.         node() { f = line(); l = nullptr; r = nullptr; }
  23.         node(int a, int b) { f = line(a, b); l = nullptr; r = nullptr; }
  24.         node(line v) { f = v; l = nullptr; r = nullptr; }
  25.     };
  26.  
  27.     typedef node* pnode;
  28.  
  29.     pnode root; int sz;
  30.     void init(int _sz) { sz = _sz + 1; root = nullptr; }
  31.  
  32.     void add_line(int a, int b) { line v = line(a, b); insert(v, -sz, sz, root); }
  33.     int64_t query(int x) { return query(x, -sz, sz, root); }
  34.  
  35.     void insert(line &v, int l, int r, pnode &nd)
  36.     {
  37.         if(!nd) { nd = new node(v); return; }
  38.  
  39.         int64_t trl = nd->f.eval(l), trr = nd->f.eval(r);
  40.         int64_t vl = v.eval(l), vr = v.eval(r);
  41.  
  42.         if(trl >= vl && trr >= vr) return;
  43.         if(trl < vl && trr < vr) { nd->f = v; return; }
  44.  
  45.         int mid = (l + r) >> 1;
  46.         if(trl < vl) swap(nd->f, v);
  47.         if(nd->f.eval(mid) > v.eval(mid)) insert(v, mid + 1, r, nd->r);
  48.         else swap(nd->f, v), insert(v, l, mid, nd->l);
  49.     }
  50.  
  51.     int64_t query(int x, int l, int r, pnode &nd)
  52.     {
  53.         if(!nd) return -inf;
  54.         if(l == r) return nd->f.eval(x);
  55.  
  56.         int mid = (l + r) >> 1;
  57.         if(mid >= x) return max(nd->f.eval(x), query(x, l, mid, nd->l));
  58.         return max(nd->f.eval(x), query(x, mid + 1, r, nd->r));
  59.     }
  60. };
  61.  
  62. struct LiChao_min
  63. {
  64.     struct line
  65.     {
  66.         int a, b;
  67.         line() { a = 0; b = 0; }
  68.         line(int _a, int _b) { a = _a; b = _b; }
  69.         int64_t eval(int x) { return a * 1ll * x + (int64_t)b; }
  70.     };
  71.  
  72.     struct node
  73.     {
  74.         node *l, *r; line f;
  75.  
  76.         node() { f = line(); l = nullptr; r = nullptr; }
  77.         node(int a, int b) { f = line(a, b); l = nullptr; r = nullptr; }
  78.         node(line v) { f = v; l = nullptr; r = nullptr; }
  79.     };
  80.  
  81.     typedef node* pnode;
  82.  
  83.     pnode root; int sz;
  84.     void init(int _sz) { sz = _sz + 1; root = nullptr; }
  85.  
  86.     void add_line(int a, int b) { line v = line(a, b); insert(v, -sz, sz, root); }
  87.     int64_t query(int x) { return query(x, -sz, sz, root); }
  88.  
  89.     void insert(line &v, int l, int r, pnode &nd)
  90.     {
  91.         if(!nd) { nd = new node(v); return; }
  92.  
  93.         int64_t trl = nd->f.eval(l), trr = nd->f.eval(r);
  94.         int64_t vl = v.eval(l), vr = v.eval(r);
  95.  
  96.         if(trl <= vl && trr <= vr) return;
  97.         if(trl > vl && trr > vr) { nd->f = v; return; }
  98.  
  99.         int mid = (l + r) >> 1;
  100.         if(trl > vl) swap(nd->f, v);
  101.         if(nd->f.eval(mid) < v.eval(mid)) insert(v, mid + 1, r, nd->r);
  102.         else swap(nd->f, v), insert(v, l, mid, nd->l);
  103.     }
  104.  
  105.     int64_t query(int x, int l, int r, pnode &nd)
  106.     {
  107.         if(!nd) return inf;
  108.         if(l == r) return nd->f.eval(x);
  109.  
  110.         int mid = (l + r) >> 1;
  111.         if(mid >= x) return min(nd->f.eval(x), query(x, l, mid, nd->l));
  112.         return min(nd->f.eval(x), query(x, mid + 1, r, nd->r));
  113.     }
  114. };
  115.  
  116. void read()
  117. {
  118.  
  119. }
  120.  
  121. void solve()
  122. {
  123.  
  124. }
  125.  
  126. int main()
  127. {
  128.     ios_base::sync_with_stdio(false);
  129.     cin.tie(NULL);
  130.  
  131.     read();
  132.     solve();
  133.     return 0;
  134. }
RAW Paste Data