fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ===================================================================
  5. // This file contains a collection of algorithms based on the
  6. // "Hilbert Order" (a space-filling curve) and "Mo's Algorithm".
  7. //
  8. // Mo's Algorithm: An offline technique to answer many range queries
  9. // (e.g., [L, R]) on a static array. "Offline" means we read ALL
  10. // queries first, reorder them to minimize the movement of two pointers
  11. // (left and right), and then answer them in that order.
  12. //
  13. // Hilbert Order: A fancy way to draw a continuous curve through all
  14. // points in a 2D grid. By ordering our queries (L, R) along this curve,
  15. // we ensure that queries that are close together (similar L and R)
  16. // are processed together, which minimizes the total number of pointer
  17. // moves. This makes Mo's Algorithm very fast in practice.
  18. //
  19. // Each function is ready to be used as a "black box".
  20. // Read the comments above each one to understand:
  21. //   - What it solves
  22. //   - What input it expects
  23. //   - What it returns
  24. //   - Time complexity
  25. //   - Important constraints / assumptions
  26. // ===================================================================
  27.  
  28. // ===================================================================
  29. // 1) CORE HILBERT ORDER FUNCTION
  30. //    This function assigns a unique integer "order" to a point (x, y)
  31. //    on a 2D grid. Points that are physically close to each other
  32. //    will have close order values.
  33. // ===================================================================
  34.  
  35. // 1.1) Calculate the Hilbert Order value for a point (x, y).
  36. //      Parameters:
  37. //        - x, y: the coordinates of the point (must be >= 0).
  38. //        - pow: the grid size is 2^pow x 2^pow. So if pow = 20, max
  39. //          coordinate is about 1,048,575.
  40. //        - rot: rotation parameter, usually pass 0.
  41. //      Returns:
  42. //        - A long long integer representing the order on the Hilbert curve.
  43. //      Time complexity: O(pow) which is effectively O(log N) since pow is small (~20).
  44. //      Constraint: x and y must be < 2^pow.
  45. //      Note: The lower the difference between two order values, the closer
  46. //            the points are in the 2D grid.
  47. long long hilbertOrder(int x, int y, int pow, int rot) {
  48.     if (pow == 0) return 0;
  49.     int hpow = 1 << (pow - 1);          // half of the current block size
  50.     int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
  51.     seg = (seg + rot) & 3;              // apply rotation
  52.     static const int rotateDelta[4] = {3, 0, 0, 1};
  53.     int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
  54.     int nrot = (rot + rotateDelta[seg]) & 3;
  55.     long long subSquareSize = 1LL << (2 * pow - 2); // size of the quadrant
  56.     long long ans = seg * subSquareSize;
  57.     long long add = hilbertOrder(nx, ny, pow - 1, nrot);
  58.     ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
  59.     return ans;
  60. }
  61.  
  62. // ===================================================================
  63. // 2) MO'S ALGORITHM FRAMEWORK
  64. //    This section provides the structures and comparators needed to
  65. //    sort queries for Mo's Algorithm.
  66. // ===================================================================
  67.  
  68. // 2.1) A structure to represent a range query.
  69. //      Parameters:
  70. //        - l: left index of the range (0-based, inclusive).
  71. //        - r: right index of the range (0-based, inclusive).
  72. //        - idx: the original index of the query (to store answers).
  73. //        - order: the Hilbert order value (filled automatically).
  74. struct MoQuery {
  75.     int l, r, idx;
  76.     long long order;
  77. };
  78.  
  79. // 2.2) Comparator to sort queries by their Hilbert order.
  80. //      Parameters:
  81. //        - a, b: two MoQuery objects.
  82. //      Returns:
  83. //        - true if a should come before b.
  84. //      Time complexity: O(1).
  85. //      Note: This is the main trick! Sorting by this order minimizes
  86. //            the total movement of the L and R pointers.
  87. bool cmpByHilbert(const MoQuery& a, const MoQuery& b) {
  88.     return a.order < b.order;
  89. }
  90.  
  91. // 2.3) Alternative comparator for Mo's Algorithm using block decomposition.
  92. //      This is the classic way to sort queries (by block of L, then R).
  93. //      Hilbert order is usually faster, but this is easier to understand.
  94. //      Parameters:
  95. //        - a, b: two MoQuery objects.
  96. //        - blockSize: the size of the block (usually sqrt(N)).
  97. //      Returns:
  98. //        - true if a should come before b.
  99. bool cmpByBlock(const MoQuery& a, const MoQuery& b, int blockSize) {
  100.     int blockA = a.l / blockSize;
  101.     int blockB = b.l / blockSize;
  102.     if (blockA != blockB) return blockA < blockB;
  103.     // To optimize for odd/even blocks (reduce pointer jumps), we
  104.     // alternate the sorting order of R.
  105.     if (blockA & 1) return a.r > b.r;
  106.     return a.r < b.r;
  107. }
  108.  
  109. // ===================================================================
  110. // 3) EXAMPLE: COUNT DISTINCT ELEMENTS IN RANGE
  111. //    This is the classic "Hello World" problem for Mo's Algorithm.
  112. //    We maintain a frequency map `freq` for the current window [L, R].
  113. //    When we move a pointer, we update the frequency and the answer.
  114. // ===================================================================
  115.  
  116. // 3.1) Process queries to count distinct elements in each range.
  117. //      This function demonstrates how to use the Hilbert order sorting
  118. //      to answer a specific problem.
  119. //      Parameters:
  120. //        - arr: the original array of integers (size N).
  121. //        - queries: a vector of MoQuery objects. Their 'l', 'r', and 'idx'
  122. //          must be filled. The function will fill the 'order' field and sort them.
  123. //      Returns:
  124. //        - A vector of integers containing the answer for each query
  125. //          (in the same order as the original queries).
  126. //      Time complexity: O((N + Q) * sqrt(N)) roughly, but Hilbert
  127. //        reduces the constant factor significantly.
  128. //      Constraint: arr elements can be any int (we use unordered_map).
  129. vector<int> moDistinctElements(const vector<int>& arr, vector<MoQuery>& queries) {
  130.     int n = arr.size();
  131.     int q = queries.size();
  132.  
  133.     // Calculate Hilbert order for each query.
  134.     // pow = 20 is enough for N up to ~1e6.
  135.     for (auto &qu : queries) {
  136.         // We treat the point as (L, R) in 2D space.
  137.         qu.order = hilbertOrder(qu.l, qu.r, 20, 0);
  138.     }
  139.  
  140.     // Sort queries using the Hilbert comparator.
  141.     sort(queries.begin(), queries.end(), cmpByHilbert);
  142.  
  143.     // Data structures for the current window.
  144.     unordered_map<int, int> freq; // frequency of each value in the window.
  145.     int curL = 0, curR = -1;      // current window boundaries (inclusive).
  146.     int curAns = 0;               // number of distinct elements in current window.
  147.  
  148.     // Lambda (small function) to add an element at index 'idx' to the window.
  149.     auto add = [&](int idx) {
  150.         int val = arr[idx];
  151.         freq[val]++;
  152.         if (freq[val] == 1) curAns++;
  153.     };
  154.  
  155.     // Lambda to remove an element at index 'idx' from the window.
  156.     auto remove = [&](int idx) {
  157.         int val = arr[idx];
  158.         freq[val]--;
  159.         if (freq[val] == 0) curAns--;
  160.     };
  161.  
  162.     vector<int> answers(q);
  163.     for (auto &qu : queries) {
  164.         // Move the left and right pointers to match the current query [qu.l, qu.r].
  165.         while (curL > qu.l) add(--curL);
  166.         while (curR < qu.r) add(++curR);
  167.         while (curL < qu.l) remove(curL++);
  168.         while (curR > qu.r) remove(curR--);
  169.  
  170.         // The answer for this query is the number of distinct elements.
  171.         answers[qu.idx] = curAns;
  172.     }
  173.     return answers;
  174. }
  175.  
  176. // ===================================================================
  177. // 4) ADVANCED: MO'S ALGORITHM WITH UPDATES (3D MO)
  178. //    Solves problems where array elements can change between queries.
  179. //    This adds a third dimension: "time" (the update index).
  180. // ===================================================================
  181.  
  182. // 4.1) Structure for a 3D query (range [L, R] at time T).
  183. //      Parameters:
  184. //        - l, r: the range boundaries.
  185. //        - t: the time (how many updates were applied before this query).
  186. //        - idx: original index of the query.
  187. struct MoQuery3D {
  188.     int l, r, t, idx;
  189. };
  190.  
  191. // 4.2) Structure for an update operation.
  192. //      Parameters:
  193. //        - pos: the index in the array to update.
  194. //        - newVal: the value to set at `pos`.
  195. //        - oldVal: the previous value at `pos` (needed to rollback).
  196. struct Update {
  197.     int pos, newVal, oldVal;
  198. };
  199.  
  200. // 4.3) Comparator for 3D Mo's Algorithm.
  201. //      Sorts by block of L, then block of R, then time.
  202. //      Parameters:
  203. //        - a, b: two MoQuery3D objects.
  204. //        - blockSize: the size of the L block (usually N^(2/3)).
  205. //      Returns:
  206. //        - true if a should come before b.
  207. bool cmpByBlock3D(const MoQuery3D& a, const MoQuery3D& b, int blockSize) {
  208.     int blockA_L = a.l / blockSize;
  209.     int blockB_L = b.l / blockSize;
  210.     if (blockA_L != blockB_L) return blockA_L < blockB_L;
  211.     int blockA_R = a.r / blockSize;
  212.     int blockB_R = b.r / blockSize;
  213.     if (blockA_R != blockB_R) return blockA_R < blockB_R;
  214.     return a.t < b.t;
  215. }
  216.  
  217. // 4.4) Process 3D queries.
  218. //      Note: This function is a template. You must supply your own
  219. //      `add`, `remove`, and `applyUpdate` logic depending on the problem.
  220. //      Parameters:
  221. //        - arr: the initial array (will be copied/modified internally).
  222. //        - queries: vector of 3D queries.
  223. //        - updates: vector of updates (chronological).
  224. //      Returns:
  225. //        - vector of answers in the original order.
  226. //      Time complexity: O((N + Q) * N^(2/3)).
  227. //      Block size: we use ceil(N^(2/3)) (approximately).
  228. vector<int> moWithUpdates(vector<int> arr, vector<MoQuery3D>& queries, vector<Update>& updates) {
  229.     int n = arr.size();
  230.     int q = queries.size();
  231.     int u = updates.size();
  232.  
  233.     // Determine optimal block size for 3D Mo.
  234.     int blockSize = pow(n, 2.0/3.0) + 1;   // +1 to avoid precision issues
  235.     sort(queries.begin(), queries.end(), [&](const MoQuery3D& a, const MoQuery3D& b) {
  236.         return cmpByBlock3D(a, b, blockSize);
  237.     });
  238.  
  239.     vector<int> answers(q);
  240.     int curL = 0, curR = -1, curT = 0;
  241.     int curAns = 0; // This depends on the problem.
  242.     unordered_map<int, int> freq; // Frequency data structure.
  243.  
  244.     // --- LAMBDA FUNCTIONS (YOU MUST FILL THESE BASED ON YOUR PROBLEM) ---
  245.     // Here is an example for counting distinct elements.
  246.     auto add = [&](int idx) {
  247.         int val = arr[idx];
  248.         freq[val]++;
  249.         if (freq[val] == 1) curAns++;
  250.     };
  251.     auto remove = [&](int idx) {
  252.         int val = arr[idx];
  253.         freq[val]--;
  254.         if (freq[val] == 0) curAns--;
  255.     };
  256.     auto applyUpdate = [&](int idx, int newVal) {
  257.         // Apply a point update to the array.
  258.         // idx: index in the array. newVal: the value to change it to.
  259.         int oldVal = arr[idx];
  260.         // If the update position is inside the current window, we must
  261.         // update our data structure first.
  262.         if (curL <= idx && idx <= curR) {
  263.             freq[oldVal]--;
  264.             if (freq[oldVal] == 0) curAns--;
  265.             freq[newVal]++;
  266.             if (freq[newVal] == 1) curAns++;
  267.         }
  268.         arr[idx] = newVal;
  269.     };
  270.     // ------------------------------------------------
  271.  
  272.     for (auto &qu : queries) {
  273.         // Move time pointer forward.
  274.         while (curT < qu.t) {
  275.             applyUpdate(updates[curT].pos, updates[curT].newVal);
  276.             curT++;
  277.         }
  278.         // Move time pointer backward.
  279.         while (curT > qu.t) {
  280.             curT--;
  281.             applyUpdate(updates[curT].pos, updates[curT].oldVal);
  282.         }
  283.         // Move L and R pointers (same as standard Mo).
  284.         while (curL > qu.l) add(--curL);
  285.         while (curR < qu.r) add(++curR);
  286.         while (curL < qu.l) remove(curL++);
  287.         while (curR > qu.r) remove(curR--);
  288.  
  289.         answers[qu.idx] = curAns;
  290.     }
  291.     return answers;
  292. }
  293.  
  294. // ===================================================================
  295. // 5) ADVANCED: MO'S ALGORITHM ON TREES
  296. //    Solves path queries on a tree (e.g., distinct values on a path).
  297. //    Uses Euler Tour to convert a tree path into a range query.
  298. // ===================================================================
  299.  
  300. // 5.1) Flatten a tree using Euler Tour (2*N length).
  301. //      Parameters:
  302. //        - adj: adjacency list of the tree (0-based).
  303. //        - root: the root node of the tree (usually 0).
  304. //      Returns:
  305. //        - euler: vector containing each node when entered and exited.
  306. //        - first: first occurrence index of each node in euler.
  307. //        - last: last occurrence index of each node in euler.
  308. //      Time complexity: O(N).
  309. //      Explanation:
  310. //        - When we enter node u, we push u to euler.
  311. //        - Then we traverse its children.
  312. //        - When we exit node u, we push u to euler again.
  313. //        - A path between u and v becomes a range query on this euler tour.
  314. void flattenTree(const vector<vector<int>>& adj, int root,
  315.                  vector<int>& euler, vector<int>& first, vector<int>& last) {
  316.     int n = adj.size();
  317.     first.assign(n, -1);
  318.     last.assign(n, -1);
  319.     euler.clear();
  320.     euler.reserve(2 * n);
  321.  
  322.     function<void(int, int)> dfs = [&](int u, int p) {
  323.         first[u] = euler.size();
  324.         euler.push_back(u);
  325.         for (int v : adj[u]) {
  326.             if (v == p) continue;
  327.             dfs(v, u);
  328.         }
  329.         last[u] = euler.size();
  330.         euler.push_back(u);
  331.     };
  332.     dfs(root, -1);
  333. }
  334.  
  335. // 5.2) Process path queries on a tree using Mo's Algorithm.
  336. //      Example: Count distinct values on the path between u and v.
  337. //      Parameters:
  338. //        - values: value of each node.
  339. //        - adj: adjacency list.
  340. //        - queries: list of {u, v} pairs (0-based).
  341. //      Returns:
  342. //        - vector of answers.
  343. //      Time complexity: O((N+Q) * sqrt(N)).
  344. //      Constraint: Works for trees (no cycles). Values can be any int.
  345. //      Trick:
  346. //        - If first[u] > first[v], swap(u, v).
  347. //        - Let LCA = lca(u, v).
  348. //        - If LCA == u, the range is [first[u], first[v]].
  349. //        - Else, the range is [last[u], first[v]] and we must add LCA separately.
  350. vector<int> moOnTreeQueries(const vector<int>& values, const vector<vector<int>>& adj,
  351.                             vector<pair<int, int>>& treeQueries) {
  352.     int n = adj.size();
  353.     int q = treeQueries.size();
  354.  
  355.     // 1. Flatten the tree.
  356.     vector<int> euler, first, last;
  357.     flattenTree(adj, 0, euler, first, last);
  358.  
  359.     // 2. Precompute LCA (using Binary Lifting).
  360.     int LOG = 1;
  361.     while ((1 << LOG) <= n) LOG++;
  362.     vector<vector<int>> up(n, vector<int>(LOG));
  363.     vector<int> depth(n, 0);
  364.     function<void(int,int)> dfs_lca = [&](int u, int p) {
  365.         up[u][0] = p;
  366.         for (int j = 1; j < LOG; j++) {
  367.             up[u][j] = up[ up[u][j-1] ][j-1];
  368.         }
  369.         for (int v : adj[u]) {
  370.             if (v == p) continue;
  371.             depth[v] = depth[u] + 1;
  372.             dfs_lca(v, u);
  373.         }
  374.     };
  375.     dfs_lca(0, 0);
  376.     auto lca = [&](int u, int v) {
  377.         if (depth[u] < depth[v]) swap(u, v);
  378.         int diff = depth[u] - depth[v];
  379.         for (int j = LOG-1; j >= 0; j--) {
  380.             if (diff & (1 << j)) u = up[u][j];
  381.         }
  382.         if (u == v) return u;
  383.         for (int j = LOG-1; j >= 0; j--) {
  384.             if (up[u][j] != up[v][j]) {
  385.                 u = up[u][j];
  386.                 v = up[v][j];
  387.             }
  388.         }
  389.         return up[u][0];
  390.     };
  391.  
  392.     // 3. Build Mo queries.
  393.     vector<MoQuery> moQueries;
  394.     moQueries.reserve(q);
  395.     vector<int> lcaNode(q, -1);
  396.     for (int i = 0; i < q; i++) {
  397.         int u = treeQueries[i].first;
  398.         int v = treeQueries[i].second;
  399.         int w = lca(u, v);
  400.         lcaNode[i] = w;
  401.  
  402.         if (first[u] > first[v]) swap(u, v);
  403.         if (w == u) {
  404.             moQueries.push_back({first[u], first[v], i, 0});
  405.         } else {
  406.             moQueries.push_back({last[u], first[v], i, 0});
  407.         }
  408.     }
  409.  
  410.     // 4. Process Mo queries (using Hilbert order).
  411.     //    We use an unordered_map for frequencies (supports any integer values).
  412.     unordered_map<int, int> freq;           // frequency of node values
  413.     vector<bool> inWindow(n, false);        // whether a node's value is currently counted
  414.     int curAns = 0;
  415.     auto addNode = [&](int nodeIdx) {
  416.         int node = euler[nodeIdx];
  417.         int val = values[node];
  418.         if (inWindow[node]) {
  419.             freq[val]--;
  420.             if (freq[val] == 0) curAns--;
  421.         } else {
  422.             freq[val]++;
  423.             if (freq[val] == 1) curAns++;
  424.         }
  425.         inWindow[node] = !inWindow[node];
  426.     };
  427.  
  428.     // Sort queries by Hilbert order.
  429.     for (auto &qu : moQueries) {
  430.         qu.order = hilbertOrder(qu.l, qu.r, 20, 0);
  431.     }
  432.     sort(moQueries.begin(), moQueries.end(), cmpByHilbert);
  433.  
  434.     vector<int> ans(q);
  435.     int curL = 0, curR = -1;
  436.     for (auto &qu : moQueries) {
  437.         while (curL > qu.l) addNode(--curL);
  438.         while (curR < qu.r) addNode(++curR);
  439.         while (curL < qu.l) addNode(curL++);
  440.         while (curR > qu.r) addNode(curR--);
  441.  
  442.         // If the LCA is not part of the range, we need to add it manually.
  443.         int l = lcaNode[qu.idx];
  444.         if (inWindow[l]) {
  445.             ans[qu.idx] = curAns;
  446.         } else {
  447.             // Add LCA temporarily, compute answer, then remove it.
  448.             int val = values[l];
  449.             freq[val]++;
  450.             if (freq[val] == 1) curAns++;
  451.             ans[qu.idx] = curAns;
  452.             freq[val]--;
  453.             if (freq[val] == 0) curAns--;
  454.         }
  455.     }
  456.     return ans;
  457. }
  458.  
  459. // ===================================================================
  460. // 6) TRICKS & PATTERNS FOR COMPETITIONS
  461. //    Additional useful utilities that rely on the Hilbert ordering
  462. //    or general two-pointer advancements.
  463. // ===================================================================
  464.  
  465. // 6.1) Count subarrays with sum in range [L, R] supporting NEGATIVE numbers.
  466. //      Parameters:
  467. //        - nums: vector of integers (can be negative!).
  468. //        - L, R: the lower and upper bounds for the sum.
  469. //      Returns:
  470. //        - The number of subarrays with sum in [L, R].
  471. //      Time complexity: O(N log N).
  472. //      How it works:
  473. //        1. Compute prefix sums P[0..N].
  474. //        2. We need to count pairs (i < j) such that L <= P[j] - P[i] <= R.
  475. //        3. As we iterate j from 0 to N, we count how many previous P[i]
  476. //           are in the range [P[j] - R, P[j] - L] using a Fenwick tree.
  477. //      Constraints: Works for all integers (positive, negative, zero).
  478. long long countSubarraysInRangeWithNegatives(const vector<int>& nums, long long L, long long R) {
  479.     int n = nums.size();
  480.     vector<long long> pref(n + 1, 0);
  481.     for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + nums[i];
  482.  
  483.     // Coordinate compression for all values we will query or update.
  484.     vector<long long> coords;
  485.     coords.reserve(3 * (n + 1));
  486.     for (long long x : pref) {
  487.         coords.push_back(x);
  488.         coords.push_back(x - L);
  489.         coords.push_back(x - R);
  490.     }
  491.     sort(coords.begin(), coords.end());
  492.     coords.erase(unique(coords.begin(), coords.end()), coords.end());
  493.  
  494.     auto getIdx = [&](long long x) {
  495.         return int(lower_bound(coords.begin(), coords.end(), x) - coords.begin()) + 1;
  496.     };
  497.  
  498.     // Fenwick Tree (Binary Indexed Tree) for prefix sums.
  499.     struct Fenwick {
  500.         int size;
  501.         vector<int> bit;
  502.         Fenwick(int s) : size(s), bit(s + 2, 0) {}
  503.         void update(int idx, int delta) {
  504.             while (idx <= size) {
  505.                 bit[idx] += delta;
  506.                 idx += idx & -idx;
  507.             }
  508.         }
  509.         int query(int idx) {
  510.             int sum = 0;
  511.             while (idx > 0) {
  512.                 sum += bit[idx];
  513.                 idx -= idx & -idx;
  514.             }
  515.             return sum;
  516.         }
  517.         int rangeQuery(int l, int r) {
  518.             if (l > r) return 0;
  519.             return query(r) - query(l - 1);
  520.         }
  521.     };
  522.  
  523.     Fenwick ft(coords.size());
  524.     long long ans = 0;
  525.     for (long long x : pref) {
  526.         // We need previous P[i] >= x - R and <= x - L.
  527.         int left = getIdx(x - R);
  528.         int right = getIdx(x - L);
  529.         ans += ft.rangeQuery(left, right);
  530.         ft.update(getIdx(x), 1);
  531.     }
  532.     return ans;
  533. }
  534.  
  535. // 6.2) Find the maximum sum of a subarray with length at least K.
  536. //      Uses a prefix sum and a sliding window minimum (two-pointer/monotonic).
  537. //      Parameters:
  538. //        - nums: vector of integers (can be negative).
  539. //        - k: minimum length of the subarray.
  540. //      Returns:
  541. //        - The maximum subarray sum with length >= k.
  542. //      Time complexity: O(N).
  543. //      Trick: Maintain the minimum prefix sum seen so far that is at least
  544. //             k steps behind the current position.
  545. long long maxSubarraySumAtLeastK(const vector<int>& nums, int k) {
  546.     int n = nums.size();
  547.     vector<long long> pref(n + 1, 0);
  548.     for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + nums[i];
  549.  
  550.     long long ans = LLONG_MIN;
  551.     deque<int> dq; // stores indices of prefix sums in increasing order of value.
  552.     for (int i = 0; i <= n; i++) {
  553.         // Remove indices that are too far away (i - idx < k -> idx <= i - k).
  554.         while (!dq.empty() && dq.front() < i - k) dq.pop_front();
  555.         // If we have a valid previous prefix, check the sum.
  556.         if (!dq.empty()) {
  557.             ans = max(ans, pref[i] - pref[dq.front()]);
  558.         }
  559.         // Maintain monotonicity (increasing values).
  560.         while (!dq.empty() && pref[dq.back()] >= pref[i]) dq.pop_back();
  561.         dq.push_back(i);
  562.     }
  563.     return ans;
  564. }
  565.  
  566. // 6.3) Minimum operations to make all elements equal (using median).
  567. //      This is a classic problem: each operation changes an element by +1/-1.
  568. //      The optimal target is the median.
  569. long long minOperationsToMakeEqual(vector<int>& nums) {
  570.     int n = nums.size();
  571.     if (n == 0) return 0;
  572.     sort(nums.begin(), nums.end());
  573.     int median = nums[n / 2];
  574.     long long totalCost = 0;
  575.     for (int x : nums) {
  576.         totalCost += std::abs((long long)x - (long long)median);
  577.     }
  578.     return totalCost;
  579. }
  580.  
  581. // 6.4) Maximum number of pairs (one from A, one from B) with sum <= K.
  582. //      Greedy algorithm using two pointers on sorted arrays.
  583. //      Parameters:
  584. //        - a, b: vectors of integers.
  585. //        - K: upper bound for the sum.
  586. //      Returns:
  587. //        - Maximum number of disjoint pairs.
  588. //      Time complexity: O(N log N + M log M).
  589. int maxPairsWithSumAtMostK(vector<int>& a, vector<int>& b, int K) {
  590.     sort(a.begin(), a.end());
  591.     sort(b.begin(), b.end());
  592.     int i = 0, j = b.size() - 1;
  593.     int ans = 0;
  594.     while (i < a.size() && j >= 0) {
  595.         if (a[i] + b[j] <= K) {
  596.             ans++;
  597.             i++;
  598.             j--;
  599.         } else {
  600.             j--;
  601.         }
  602.     }
  603.     return ans;
  604. }
  605.  
  606. // ===================================================================
  607. // 7) GENERIC TWO-POINTER PATTERN (Placeholder reminder)
  608. // ===================================================================
  609. template<typename T>
  610. int twoPointerPlaceholder(const vector<T>& arr) {
  611.     int l = 0, r = arr.size() - 1;
  612.     int ans = 0;
  613.     while (l < r) {
  614.         // Update ans based on arr[l], arr[r].
  615.         // Move l++ or r-- based on a condition.
  616.         if (arr[l] + arr[r] < 0) l++;
  617.         else r--;
  618.     }
  619.     return ans;
  620. }
  621.  
  622. // ===================================================================
  623. // main() - Demonstration of how to use these black boxes.
  624. // ===================================================================
  625. int main() {
  626.     ios::sync_with_stdio(false);
  627.     cin.tie(nullptr);
  628.  
  629.     // Example 1: Distinct elements in range queries.
  630.     vector<int> arr = {1, 2, 1, 3, 4, 2, 1};
  631.     vector<MoQuery> queries = {
  632.         {1, 4, 0, 0}, // query 0: range [1, 4] -> 2,1,3,4 -> distinct = 4
  633.         {0, 2, 1, 0}, // query 1: range [0, 2] -> 1,2,1 -> distinct = 2
  634.         {2, 5, 2, 0}  // query 2: range [2, 5] -> 1,3,4,2 -> distinct = 4
  635.     };
  636.     vector<int> distinctAnswers = moDistinctElements(arr, queries);
  637.     for (int i = 0; i < distinctAnswers.size(); i++) {
  638.         cout << "Distinct in query " << i << ": " << distinctAnswers[i] << "\n";
  639.     }
  640.  
  641.     // Example 2: Count subarrays with sum in [L, R] supporting negative numbers.
  642.     vector<int> nums = {1, -2, 3, -4, 5};
  643.     long long L = 1, R = 3;
  644.     long long cnt = countSubarraysInRangeWithNegatives(nums, L, R);
  645.     cout << "Number of subarrays with sum in [1, 3]: " << cnt << "\n";
  646.  
  647.     // Example 3: Maximum subarray sum with length at least 2.
  648.     vector<int> nums2 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
  649.     cout << "Max subarray sum with length >= 2: " << maxSubarraySumAtLeastK(nums2, 2) << "\n";
  650.  
  651.     return 0;
  652. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Distinct in query 0: 4
Distinct in query 1: 2
Distinct in query 2: 4
Number of subarrays with sum in [1, 3]: 7
Max subarray sum with length >= 2: 4
https://ideone.com/Q579he
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!