peltorator

Li Chao Segment Tree Insert Line On Segment

May 15th, 2021 (edited)
240
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.         }
  40.         if (dominateLeft == dominateMid) {
  41.             insertLine(2 * v + 1, mid, r, newLine);
  42.         } else {
  43.             insertLine(2 * v, l, mid, newLine);
  44.         }
  45.     }
  46.  
  47.     void insertLineOnSegment(int v, int l, int r, int ql, int qr, Line newLine) {
  48.         if (r <= ql || qr <= l) {
  49.             return;
  50.         }
  51.         if (ql <= l && r <= qr) {
  52.             insertLine(v, l, r, newLine);
  53.             return;
  54.         }
  55.         int mid = (r + l) / 2;
  56.         insertLineOnSegment(2 * v, l, mid, ql, qr, newLine);
  57.         insertLineOnSegment(2 * v + 1, mid, r, ql, qr, newLine);
  58.     }
  59.  
  60.     void insertLineOnSegment(int ql, int qr, Line newLine) {
  61.         insertLineOnSegment(1, 0, n, ql, qr, newLine);
  62.     }
  63.  
  64.     long long getValue(int v, int l, int r, int pos) {
  65.         long long ans = tree[v](pos);
  66.         if (l + 1 != r) {
  67.             int mid = (r + l) / 2;
  68.             if (pos < mid) {
  69.                 ans = min(ans, getValue(2 * v, l, mid, pos));
  70.             } else {
  71.                 ans = min(ans, getValue(2 * v + 1, mid, r, pos));
  72.             }
  73.         }
  74.         return ans;
  75.     }
  76.  
  77.     long long getValue(int pos) {
  78.         return getValue(1, 0, n, pos);
  79.     }
  80.  
  81. } segTree;
  82.  
  83. int main() {
  84.     ios::sync_with_stdio(0);
  85.     cin.tie(0);
  86.  
  87.     int n;
  88.     cin >> n;
  89.     segTree.init(n);
  90.  
  91.     int q;
  92.     cin >> q;
  93.     for (int i = 0; i < q; i++) {
  94.         int type;
  95.         cin >> type;
  96.         if (type == 1) {
  97.             int l, r, k, b;
  98.             cin >> l >> r >> k >> b;
  99.             l--;
  100.             segTree.insertLineOnSegment(l, r, Line(k, b));
  101.         } else {
  102.             int x;
  103.             cin >> x;
  104.             cout << segTree.getValue(x) << '\n';
  105.         }
  106.     }
  107. }
  108.  
RAW Paste Data