fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. using ld = long double;
  6.  
  7. // =====================================================================
  8. // COLLECTION OF CONVEX HULL TRICK (CHT) / LINE CONTAINER ALGORITHMS
  9. // =====================================================================
  10. //
  11. // This file provides multiple implementations of data structures that
  12. // store linear functions y = m*x + b and support:
  13. //   1. Adding a line.
  14. //   2. Querying the minimum (or maximum) y at a given x.
  15. //
  16. // Use cases:
  17. //   - Optimizing DP transitions of the form:
  18. //       dp[i] = min_j ( dp[j] + a[i]*b[j] + c[j] )
  19. //     where each j is a line (m = b[j], b = dp[j] + c[j]) and
  20. //     a[i] is the query x.
  21. //
  22. // Each structure below has its own strengths and constraints.
  23. // Read the comments above each to choose the right one.
  24. // =====================================================================
  25.  
  26. // =====================================================================
  27. // 1) LineContainer (KACTL implementation)
  28. //    =====================================
  29. //    General-purpose, supports adding lines in ANY order and querying
  30. //    at ANY x.  Uses a multiset to maintain the lower envelope.
  31. //
  32. //    HOW TO USE:
  33. //       LineContainer cht;
  34. //       cht.add(2, 5);      // adds y = 2*x + 5
  35. //       cht.add(-1, 3);     // adds y = -1*x + 3
  36. //       ll ans = cht.query(4);  // returns minimum y at x = 4
  37. //
  38. //    For MAXIMUM queries: store lines as (-m, -b) and negate the result.
  39. //
  40. //    TIME COMPLEXITY:
  41. //       add(line)  : O(log N) amortized.
  42. //       query(x)   : O(log N).
  43. //
  44. //    CONSTRAINTS:
  45. //       - m, b, x fit in 'long long' (up to ≈9e18).
  46. //       - Uses 'long double' only for intersection checks internally,
  47. //         but the result is computed in integer arithmetic.
  48. //       - If coordinates can exceed 1e9, multiplication may overflow
  49. //         'long long' – consider using '__int128' for the result
  50. //         (modify query to return __int128 if needed).
  51. // =====================================================================
  52. struct LineContainer {
  53.     struct Line {
  54.         mutable ll m, b, p;   // y = m*x + b,  p = first x where this line is optimal
  55.         bool operator<(const Line& o) const { return m < o.m; }
  56.         bool operator<(ll x) const { return p < x; }
  57.     };
  58.  
  59.     multiset<Line, less<>> hull;
  60.     static const ll inf = LLONG_MAX;
  61.  
  62.     // floor division for possibly negative numbers (KACTL style)
  63.     ll div(ll a, ll b) {
  64.         return a / b - ((a ^ b) < 0 && a % b);
  65.     }
  66.  
  67.     // Check if line y (pointed by iterator y) is made obsolete by x and z.
  68.     // Returns true if y should be removed.
  69.     bool isect(typename multiset<Line, less<>>::iterator x,
  70.                typename multiset<Line, less<>>::iterator y) {
  71.         if (y == hull.end()) { x->p = inf; return false; }
  72.         if (x->m == y->m) x->p = x->b > y->b ? inf : -inf;
  73.         else x->p = div(y->b - x->b, x->m - y->m);
  74.         return x->p >= y->p;
  75.     }
  76.  
  77.     // Add a new line y = m*x + b.
  78.     void add(ll m, ll b) {
  79.         auto z = hull.insert({m, b, 0});
  80.         auto y = z++;
  81.         auto x = y;
  82.  
  83.         // Remove lines to the right that become obsolete
  84.         while (isect(y, z)) z = hull.erase(z);
  85.  
  86.         // Remove lines to the left if the new line makes them obsolete
  87.         if (x != hull.begin() && isect(--x, y)) {
  88.             isect(x, y = hull.erase(y));
  89.         }
  90.  
  91.         // Further clean-up to the left
  92.         while ((y = x) != hull.begin() && (--x)->p >= y->p) {
  93.             isect(x, hull.erase(y));
  94.         }
  95.     }
  96.  
  97.     // Query the minimum y at x.
  98.     ll query(ll x) const {
  99.         auto it = hull.lower_bound(x);
  100.         if (it == hull.begin()) return it->m * x + it->b;
  101.         --it;
  102.         return it->m * x + it->b;
  103.     }
  104. };
  105.  
  106. // =====================================================================
  107. // 2) Dynamic Li Chao Tree (Node‑based)
  108. //    ==================================
  109. //    Works over a fixed integer interval [L, R] of possible x‑coordinates.
  110. //    Nodes are created on the fly, so no coordinate compression needed.
  111. //
  112. //    HOW TO USE:
  113. //       DynamicLiChao cht(0, 1e9);   // x in [0, 1e9]
  114. //       cht.add({2, 5});             // y = 2*x + 5
  115. //       ll ans = cht.query(4);       // minimum y at x = 4
  116. //
  117. //    TIME COMPLEXITY:
  118. //       add(line) : O(log (R - L))
  119. //       query(x)  : O(log (R - L))
  120. //
  121. //    CONSTRAINTS:
  122. //       - L, R fit in 'long long'.
  123. //       - Memory is O(number_of_lines * log(R-L)).
  124. //       - Works well for large ranges (e.g., up to 1e18) because depth is ~60.
  125. // =====================================================================
  126. struct DynamicLiChao {
  127.     struct Line {
  128.         ll m, b;
  129.         ll get(ll x) const { return m * x + b; }
  130.     };
  131.  
  132.     struct Node {
  133.         Line line;
  134.         Node *left, *right;
  135.         Node(Line l) : line(l), left(nullptr), right(nullptr) {}
  136.     };
  137.  
  138.     Node* root;
  139.     ll l_range, r_range;
  140.     static const ll INF = 4e18;
  141.  
  142.     DynamicLiChao(ll l, ll r) : l_range(l), r_range(r) {
  143.         root = new Node({0, INF});   // dummy line that returns INF
  144.     }
  145.  
  146.     void add(Line nw) { add(nw, root, l_range, r_range); }
  147.  
  148.     void add(Line nw, Node*& node, ll l, ll r) {
  149.         if (!node) {
  150.             node = new Node(nw);
  151.             return;
  152.         }
  153.         ll mid = l + (r - l) / 2;
  154.         Line cur = node->line;
  155.  
  156.         // Keep the better line at mid in the node
  157.         if (nw.get(mid) < cur.get(mid)) {
  158.             swap(node->line, nw);
  159.             cur = node->line;   // now cur is the line that is better at mid
  160.         }
  161.         if (l == r) return;
  162.  
  163.         // The worse line (nw) may be better on one side
  164.         if (nw.get(l) < cur.get(l)) {
  165.             add(nw, node->left, l, mid);
  166.         } else if (nw.get(r) < cur.get(r)) {
  167.             add(nw, node->right, mid + 1, r);
  168.         }
  169.         // else nw is never better in this interval
  170.     }
  171.  
  172.     ll query(ll x) { return query(root, x, l_range, r_range); }
  173.  
  174.     ll query(Node* node, ll x, ll l, ll r) {
  175.         if (!node) return INF;
  176.         ll res = node->line.get(x);
  177.         if (l == r) return res;
  178.         ll mid = l + (r - l) / 2;
  179.         if (x <= mid) return min(res, query(node->left, x, l, mid));
  180.         else return min(res, query(node->right, x, mid + 1, r));
  181.     }
  182. };
  183.  
  184. // =====================================================================
  185. // 3) Li Chao Tree with Coordinate Compression
  186. //    =========================================
  187. //    Used when all possible query x‑values are known in advance.
  188. //    Sorts and compresses them, then builds a segment tree over indices.
  189. //
  190. //    HOW TO USE:
  191. //       vector<ll> xs = {0, 3, 5, 10};   // all x that will be queried
  192. //       LiChaoCompressed cht(xs);
  193. //       cht.add({2, 5});
  194. //       cout << cht.query(3);   // 3 must be in xs
  195. //
  196. //    TIME COMPLEXITY:
  197. //       add(line) : O(log M), where M = number of distinct x
  198. //       query(x)  : O(log M)
  199. //
  200. //    CONSTRAINTS:
  201. //       - Query points must be known at construction.
  202. //       - Memory is O(4*M), faster and lighter than dynamic version.
  203. // =====================================================================
  204. struct LiChaoCompressed {
  205.     struct Line {
  206.         ll m, b;
  207.         ll get(ll x) const { return m * x + b; }
  208.     };
  209.  
  210.     vector<ll> xs;               // sorted unique coordinates
  211.     vector<Line> tree;
  212.     int n;
  213.     static const ll INF = 4e18;
  214.  
  215.     LiChaoCompressed(vector<ll> _xs) : xs(_xs) {
  216.         sort(xs.begin(), xs.end());
  217.         xs.erase(unique(xs.begin(), xs.end()), xs.end());
  218.         n = (int)xs.size();
  219.         tree.assign(4 * n, {0, INF});
  220.     }
  221.  
  222.     void add(Line nw) { add(nw, 1, 0, n - 1); }
  223.  
  224.     void add(Line nw, int node, int l, int r) {
  225.         int mid = (l + r) / 2;
  226.         ll x_l = xs[l], x_m = xs[mid], x_r = xs[r];
  227.         Line cur = tree[node];
  228.  
  229.         if (nw.get(x_m) < cur.get(x_m)) {
  230.             swap(tree[node], nw);
  231.             cur = tree[node];
  232.         }
  233.         if (l == r) return;
  234.  
  235.         if (nw.get(x_l) < cur.get(x_l)) {
  236.             add(nw, node * 2, l, mid);
  237.         } else if (nw.get(x_r) < cur.get(x_r)) {
  238.             add(nw, node * 2 + 1, mid + 1, r);
  239.         }
  240.     }
  241.  
  242.     ll query(ll x) {
  243.         int idx = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
  244.         if (idx == n || xs[idx] != x) return INF;   // x not found
  245.         return query(1, 0, n - 1, idx);
  246.     }
  247.  
  248.     ll query(int node, int l, int r, int idx) {
  249.         ll res = tree[node].get(xs[idx]);
  250.         if (l == r) return res;
  251.         int mid = (l + r) / 2;
  252.         if (idx <= mid) return min(res, query(node * 2, l, mid, idx));
  253.         else return min(res, query(node * 2 + 1, mid + 1, r, idx));
  254.     }
  255. };
  256.  
  257. // =====================================================================
  258. // 4) Monotonic CHT (Deque‑based)
  259. //    ============================
  260. //    Fastest O(1) amortized, but requires:
  261. //       - Slopes (m) added in strictly increasing (or decreasing) order.
  262. //       - Query x in strictly increasing (or decreasing) order.
  263. //    Use this only when the DP transition has these monotonic properties.
  264. //
  265. //    HOW TO USE:
  266. //       MonoCHT cht;               // slopes must be added increasing
  267. //       cht.add(2, 5);             // y = 2*x + 5
  268. //       cht.add(3, 1);             // 3 > 2, valid
  269. //       ll ans = cht.query(4);     // next query x must be >= 4
  270. //
  271. //    TIME COMPLEXITY:
  272. //       add(line) : O(1) amortized
  273. //       query(x)  : O(1) amortized
  274. //
  275. //    CONSTRAINTS:
  276. //       - Slopes strictly increasing (for minimum queries).
  277. //       - Queries non‑decreasing.
  278. //       - Use __int128 in bad() to avoid overflow when slopes/intercepts are large.
  279. // =====================================================================
  280. struct MonoCHT {
  281.     vector<ll> M, B;
  282.     int ptr = 0;
  283.  
  284.     // Check if line2 is unnecessary given line1 and line3.
  285.     // For minimum CHT with increasing slopes.
  286.     bool bad(ll m1, ll b1, ll m2, ll b2, ll m3, ll b3) {
  287.         // (b3 - b1) * (m1 - m2) <= (b2 - b1) * (m1 - m3)
  288.         return (__int128)(b3 - b1) * (m1 - m2) <= (__int128)(b2 - b1) * (m1 - m3);
  289.     }
  290.  
  291.     // Add a line y = m*x + b. Slopes must be increasing.
  292.     void add(ll m, ll b) {
  293.         // If same slope, keep the smaller intercept.
  294.         while (!M.empty() && M.back() == m) {
  295.             if (B.back() <= b) return;
  296.             M.pop_back(); B.pop_back();
  297.         }
  298.         // Remove last line if it becomes obsolete.
  299.         while (M.size() >= 2 &&
  300.                bad(M[M.size()-2], B[B.size()-2], M.back(), B.back(), m, b)) {
  301.             M.pop_back(); B.pop_back();
  302.         }
  303.         M.push_back(m);
  304.         B.push_back(b);
  305.         if (ptr >= (int)M.size()) ptr = (int)M.size() - 1;
  306.     }
  307.  
  308.     // Query the minimum y at x. x must be non‑decreasing.
  309.     ll query(ll x) {
  310.         while (ptr + 1 < (int)M.size() &&
  311.                M[ptr] * x + B[ptr] >= M[ptr + 1] * x + B[ptr + 1]) {
  312.             ptr++;
  313.         }
  314.         return M[ptr] * x + B[ptr];
  315.     }
  316. };
  317.  
  318. // =====================================================================
  319. // 5) Converting to MAXIMUM queries
  320. //    ==============================
  321. //    To find the maximum, store lines with slopes and intercepts
  322. //    multiplied by -1, then negate the query result.
  323. //
  324. //    Example:
  325. //       LineContainer cht;
  326. //       cht.add(-2, -5);          // stores -y for y = 2*x + 5
  327. //       ll max_val = -cht.query(4); // returns max(2*4+5, ...)
  328. // =====================================================================
  329.  
  330. // =====================================================================
  331. // 6) Common DP optimization pattern
  332. //    ===============================
  333. //    DP[i] = min_j ( DP[j] + A[i] * B[j] + C[j] )
  334. //
  335. //    Treat each j as a line: m = B[j], b = DP[j] + C[j].
  336. //    Query at x = A[i] to get DP[i].
  337. //
  338. //    Example skeleton:
  339. //       LineContainer cht;
  340. //       cht.add(B[0], C[0]);    // assuming DP[0] = 0
  341. //       for (int i = 1; i < n; i++) {
  342. //           dp[i] = cht.query(A[i]);
  343. //           cht.add(B[i], dp[i] + C[i]);
  344. //       }
  345. // =====================================================================
  346.  
  347. // =====================================================================
  348. // EXAMPLE USAGE (can be removed)
  349. // =====================================================================
  350. int main() {
  351.     ios::sync_with_stdio(false);
  352.     cin.tie(nullptr);
  353.  
  354.     // Test LineContainer
  355.     LineContainer cht;
  356.     cht.add(1, 0);   // y = x
  357.     cht.add(0, 5);   // y = 5
  358.     cout << cht.query(3) << "\n";   // min(3,5) = 3
  359.  
  360.     // Test DynamicLiChao
  361.     DynamicLiChao dcht(0, 10);
  362.     dcht.add({1, 0});
  363.     dcht.add({0, 5});
  364.     cout << dcht.query(3) << "\n";   // 3
  365.  
  366.     // Test MonoCHT (slopes increasing, queries increasing)
  367.     MonoCHT mcht;
  368.     mcht.add(1, 0);
  369.     mcht.add(2, -1);   // y = 2x - 1
  370.     cout << mcht.query(2) << "\n";   // min(2,3) = 2
  371.     cout << mcht.query(5) << "\n";   // queries monotonic: 2 -> 5
  372.  
  373.     // Test LiChaoCompressed
  374.     vector<ll> xs = {0, 3, 5, 10};
  375.     LiChaoCompressed lc(xs);
  376.     lc.add({1, 0});
  377.     lc.add({0, 5});
  378.     cout << lc.query(3) << "\n";   // 3
  379.  
  380.     // MAX query via negation
  381.     LineContainer max_cht;
  382.     max_cht.add(-1, 0);   // stores -y for y = x
  383.     max_cht.add(0, -5);   // stores -y for y = 5
  384.     cout << -max_cht.query(3) << "\n";   // max(3,5) = 5
  385.  
  386.     return 0;
  387. }
Success #stdin #stdout 0.01s 5264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5
3
2
5
3
3
https://ideone.com/c26C7L
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!