peltorator

Extended Li Chao Segment Tree

May 13th, 2021 (edited)
473
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.     void add(Line other) {
  19.         k += other.k;
  20.         b += other.b;
  21.     }
  22. };
  23.  
  24. struct LiChaoSegmentTree {
  25.     static const int T = (1 << 23);
  26.  
  27.     struct Node {
  28.         Line curLine;
  29.         Line pushLine = Line(0, 0);
  30.     } tree[T];
  31.  
  32.     int n;
  33.  
  34.     void init(int len) {
  35.         n = len;
  36.     }
  37.  
  38.     void doPush(int v) {
  39.         tree[2 * v].pushLine.add(tree[v].pushLine);
  40.         tree[2 * v].curLine.add(tree[v].pushLine);
  41.  
  42.         tree[2 * v + 1].pushLine.add(tree[v].pushLine);
  43.         tree[2 * v + 1].curLine.add(tree[v].pushLine);
  44.  
  45.         tree[v].pushLine = Line(0, 0);
  46.     }
  47.  
  48.     void insertLine(int v, int l, int r, Line newLine) {
  49.         bool dominateLeft = (newLine(l) < tree[v].curLine(l));
  50.         int mid = (r + l) / 2;
  51.         bool dominateMid = (newLine(mid) < tree[v].curLine(mid));
  52.         if (dominateMid) {
  53.             swap(newLine, tree[v].curLine);
  54.         }
  55.         if (l + 1 == r) {
  56.             return;
  57.         }
  58.         doPush(v);
  59.         if (dominateLeft == dominateMid) {
  60.             insertLine(2 * v + 1, mid, r, newLine);
  61.         } else {
  62.             insertLine(2 * v, l, mid, newLine);
  63.         }
  64.     }
  65.  
  66.     void insertLineOnSegment(int v, int l, int r, int ql, int qr, Line newLine) {
  67.         if (r <= ql || qr <= l) {
  68.             return;
  69.         }
  70.         if (ql <= l && r <= qr) {
  71.             insertLine(v, l, r, newLine);
  72.             return;
  73.         }
  74.         doPush(v);
  75.         int mid = (r + l) / 2;
  76.         insertLineOnSegment(2 * v, l, mid, ql, qr, newLine);
  77.         insertLineOnSegment(2 * v + 1, mid, r, ql, qr, newLine);
  78.     }
  79.  
  80.     void insertLineOnSegment(int ql, int qr, Line newLine) {
  81.         insertLineOnSegment(1, 0, n, ql, qr, newLine);
  82.     }
  83.  
  84.     void freeVertex(int v, int l, int r) {
  85.         int mid = (r + l) / 2;
  86.         insertLine(2 * v, l, mid, tree[v].curLine);
  87.         insertLine(2 * v + 1, mid, r, tree[v].curLine);
  88.         tree[v].curLine = Line();
  89.     }
  90.  
  91.     void addLineOnSegment(int v, int l, int r, int ql, int qr, Line newLine) {
  92.         if (r <= ql || qr <= l) {
  93.             return;
  94.         }
  95.         if (ql <= l && r <= qr) {
  96.             tree[v].curLine.add(newLine);
  97.             tree[v].pushLine.add(newLine);
  98.             return;
  99.         }
  100.         doPush(v);
  101.         freeVertex(v, l, r);
  102.         int mid = (r + l) / 2;
  103.         addLineOnSegment(2 * v, l, mid, ql, qr,  newLine);
  104.         addLineOnSegment(2 * v + 1, mid, r, ql, qr,  newLine);
  105.     }
  106.  
  107.     void addLineOnSegment(int ql, int qr, Line newLine) {
  108.         addLineOnSegment(1, 0, n, ql, qr, newLine);
  109.     }
  110.  
  111.     long long getValue(int v, int l, int r, int pos) {
  112.         long long ans = tree[v].curLine(pos);
  113.         if (l + 1 != r) {
  114.             doPush(v);
  115.             int mid = (r + l) / 2;
  116.             if (pos < mid) {
  117.                 ans = min(ans, getValue(2 * v, l, mid, pos));
  118.             } else {
  119.                 ans = min(ans, getValue(2 * v + 1, mid, r, pos));
  120.             }
  121.         }
  122.         return ans;
  123.     }
  124.  
  125.     long long getValue(int pos) {
  126.         return getValue(1, 0, n, pos);
  127.     }
  128.  
  129. } segTree;
  130.  
  131. int main() {
  132.     ios::sync_with_stdio(0);
  133.     cin.tie(0);
  134.  
  135.     int n;
  136.     cin >> n;
  137.     segTree.init(n);
  138.  
  139.     int q;
  140.     cin >> q;
  141.     for (int i = 0; i < q; i++) {
  142.         int type;
  143.         cin >> type;
  144.         if (type == 1) {
  145.             int l, r, k, b;
  146.             cin >> l >> r >> k >> b;
  147.             l--;
  148.             segTree.insertLineOnSegment(l, r, Line(k, b));
  149.         } else if (type == 2) {
  150.             int l, r, k, b;
  151.             cin >> l >> r >> k >> b;
  152.             l--;
  153.             segTree.addLineOnSegment(l, r, Line(k, b));
  154.         } else {
  155.             int x;
  156.             cin >> x;
  157.             cout << segTree.getValue(x) << '\n';
  158.         }
  159.     }
  160. }
RAW Paste Data