peltorator

Li Chao Segment Tree

May 13th, 2021 (edited)
122
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const long long INF = 1e18 + 7;
  6.  
  7. struct Line {
  8.     long long k, b;
  9.  
  10.     Line(long long k, long long b): k(k), b(b) {}
  11.  
  12.     Line(): k(0), b(INF) {}
  13.  
  14.     long long operator()(long long x) {
  15.         return k * x + b;
  16.     }
  17. };
  18.  
  19. struct LiChaoSegmentTree {
  20.     static const int T = (1 << 23);
  21.  
  22.     Line tree[T];
  23.  
  24.     int n;
  25.  
  26.     void init(int len) {
  27.         n = len;
  28.     }
  29.  
  30.     void insertLine(int v, int l, int r, Line newLine) {
  31.         bool dominateLeft = (newLine(l) < tree[v](l));
  32.         int mid = (r + l) / 2;
  33.         bool dominateMid = (newLine(mid) < tree[v](mid));
  34.         if (dominateMid) {
  35.             swap(newLine, tree[v]);
  36.         }
  37.         if (l + 1 == r) {
  38.             return;
  39.         } else if (dominateLeft == dominateMid) {
  40.             insertLine(2 * v + 1, mid, r, newLine);
  41.         } else {
  42.             insertLine(2 * v, l, mid, newLine);
  43.         }
  44.     }
  45.  
  46.     void insertLine(Line newLine) {
  47.         insertLine(1, 0, n, newLine);
  48.     }
  49.  
  50.     long long getValue(int v, int l, int r, int pos) {
  51.         long long ans = tree[v](pos);
  52.         if (l + 1 != r) {
  53.             int mid = (r + l) / 2;
  54.             if (pos < mid) {
  55.                 ans = min(ans, getValue(2 * v, l, mid, pos));
  56.             } else {
  57.                 ans = min(ans, getValue(2 * v + 1, mid, r, pos));
  58.             }
  59.         }
  60.         return ans;
  61.     }
  62.  
  63.     long long getValue(int pos) {
  64.         return getValue(1, 0, n, pos);
  65.     }
  66.  
  67. } segTree;
  68.  
  69. int main() {
  70.     ios::sync_with_stdio(0);
  71.     cin.tie(0);
  72.  
  73.     int n;
  74.     cin >> n;
  75.     segTree.init(n);
  76.  
  77.     int q;
  78.     cin >> q;
  79.     for (int i = 0; i < q; i++) {
  80.         int type;
  81.         cin >> type;
  82.         if (type == 1) {
  83.             int k, b;
  84.             cin >> k >> b;
  85.             segTree.insertLine(Line(k, b));
  86.         } else {
  87.             int x;
  88.             cin >> x;
  89.             cout << segTree.getValue(x) << '\n';
  90.         }
  91.     }
  92. }
RAW Paste Data