fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ===================================================================
  5. // This file contains a collection of Mo's Algorithm (with SQRT trick)
  6. // implementations. Each function is ready to be used as a "black box".
  7. //
  8. // Read the comments above each one to understand:
  9. //   - What it solves
  10. //   - What input it expects
  11. //   - What it returns
  12. //   - Time complexity
  13. //   - Important constraints / assumptions
  14. //
  15. // IMPORTANT TERMS (explained in simple English):
  16. //   - "Offline algorithm" : we need to know ALL queries before we start
  17. //                           answering any of them. We cannot answer them
  18. //                           one by one as they come.
  19. //   - "Query" : a question like "what is the sum of elements from index L to R?".
  20. //   - "Pointer" (L and R) : two integer indices that mark the current range
  21. //                           we are looking at. Moving them updates our answer.
  22. //   - "Block" : we divide the array into groups of size sqrt(N). This is
  23. //               the "SQRT trick" that makes the algorithm fast.
  24. //   - "Add / Remove" : when we move a pointer to include a new element,
  25. //                      we "add" it to our current answer. When we move out
  26. //                      of an element, we "remove" it.
  27. //   - "Frequency array" : an array that counts how many times each value
  28. //                         appears in the current range.
  29. // ===================================================================
  30.  
  31. // ===================================================================
  32. // 1) Core Structures & Helpers
  33. //    These are the basic building blocks used by all Mo functions below.
  34. // ===================================================================
  35.  
  36. // 1.1) Represents a single range query.
  37. //      Parameters:
  38. //        - l : left index of the range (0-based or 1-based, but pick one
  39. //              and stick to it. All functions here use 0-based indices).
  40. //        - r : right index of the range (inclusive).
  41. //        - idx : the index of this query in the original list (to store answers).
  42. //      Time complexity: O(1) to create.
  43. struct Query {
  44.     int l, r, idx;
  45. };
  46.  
  47. // 1.2) Represents an update for "Mo with Updates".
  48. //      Parameters:
  49. //        - pos : the index in the array where the change happens.
  50. //        - oldVal : the value before the update.
  51. //        - newVal : the value after the update.
  52. //      Time complexity: O(1) to create.
  53. struct UpdateQuery {
  54.     int pos, oldVal, newVal;
  55. };
  56.  
  57. // 1.3) Calculates the optimal block size for standard Mo's algorithm.
  58. //      Parameters:
  59. //        - n : the size of the array.
  60. //        - q : the number of queries (optional, but recommended).
  61. //      Returns:
  62. //        - an integer representing the block size.
  63. //      Time complexity: O(1)
  64. //      Constraint: n must be > 0.
  65. //      Note: using max(1, (int)(n / sqrt(q))) often gives better performance.
  66. int getMoBlockSize(int n, int q) {
  67.     if (q == 0) return max(1, (int)sqrt(n));
  68.     return max(1, (int)(n / sqrt(q)));
  69. }
  70.  
  71. // 1.4) Sorts queries in the special Mo's order.
  72. //      This is NOT a function you call directly. It is used internally
  73. //      by the process functions.
  74. //      Parameters:
  75. //        - a, b : two Query objects.
  76. //        - blockSize : the block size to use.
  77. //      Returns:
  78. //        - true if 'a' should come before 'b' in the sorted order.
  79. //      Time complexity: O(1)
  80. //      Note: The "even-odd trick" (ordering R differently based on block)
  81. //            reduces pointer movements significantly.
  82. bool moComparator(const Query& a, const Query& b, int blockSize) {
  83.     int blockA = a.l / blockSize;
  84.     int blockB = b.l / blockSize;
  85.     if (blockA != blockB) return blockA < blockB;
  86.     // Even block: sort R ascending. Odd block: sort R descending.
  87.     if (blockA & 1) return a.r > b.r;
  88.     return a.r < b.r;
  89. }
  90.  
  91. // ===================================================================
  92. // 2) Standard Mo's Algorithm (No Updates)
  93. //    These functions answer static range queries on an array.
  94. //    They all expect the array to be 0-indexed.
  95. // ===================================================================
  96.  
  97. // 2.1) Count the number of distinct elements in each query range.
  98. //      Purpose:
  99. //        - Given an array and many queries [L, R], for each query,
  100. //          tell how many different values appear in that subarray.
  101. //      Parameters:
  102. //        - arr : the input vector of integers (0-indexed).
  103. //        - queries : a vector of Query structs. Each Query must have
  104. //                    'l', 'r', and 'idx' filled. 'idx' identifies
  105. //                    which query it is.
  106. //      Returns:
  107. //        - a vector<int> where answer[i] is the number of distinct elements
  108. //          in the i-th query (ordered by the original query index).
  109. //      Time complexity: O((N + Q) * sqrt(N)) on average, where N = arr.size(),
  110. //                       Q = queries.size(). More precisely O((N+Q) * sqrt(N)).
  111. //      Constraint:
  112. //        - The array values should be compressible (coordinate compression
  113. //          is recommended if values are large). This function does NOT
  114. //          compress internally. If values exceed 1e6, use a different
  115. //          method or compress the array first.
  116. //      Notes:
  117. //        - This is the classic "Mo's algorithm" problem.
  118. //        - If you have negative numbers or large numbers (> 2e5), you MUST
  119. //          compress them (e.g., sort and map to 0..M-1) before calling.
  120. vector<int> moDistinctElements(const vector<int>& arr, const vector<Query>& queries) {
  121.     int n = arr.size();
  122.     int q = queries.size();
  123.     int blockSize = getMoBlockSize(n, q);
  124.  
  125.     // Sort the queries in the Mo order.
  126.     vector<Query> sortedQueries = queries;
  127.     sort(sortedQueries.begin(), sortedQueries.end(),
  128.          [&](const Query& a, const Query& b) {
  129.              return moComparator(a, b, blockSize);
  130.          });
  131.  
  132.     vector<int> ans(q, 0);
  133.     vector<int> freq(200005, 0); // Assumes arr values are < 200k.
  134.     // If your values are larger, compress them or change this size.
  135.  
  136.     int curL = 0, curR = -1;
  137.     int distinctCount = 0;
  138.  
  139.     auto add = [&](int pos) {
  140.         int val = arr[pos];
  141.         if (freq[val] == 0) distinctCount++;
  142.         freq[val]++;
  143.     };
  144.  
  145.     auto remove = [&](int pos) {
  146.         int val = arr[pos];
  147.         freq[val]--;
  148.         if (freq[val] == 0) distinctCount--;
  149.     };
  150.  
  151.     for (const Query& qry : sortedQueries) {
  152.         while (curL > qry.l) add(--curL);
  153.         while (curR < qry.r) add(++curR);
  154.         while (curL < qry.l) remove(curL++);
  155.         while (curR > qry.r) remove(curR--);
  156.         ans[qry.idx] = distinctCount;
  157.     }
  158.     return ans;
  159. }
  160.  
  161. // 2.2) Find the sum of elements in each query range.
  162. //      Purpose:
  163. //        - Given an array and many queries [L, R], for each query,
  164. //          calculate the total sum of arr[L] + ... + arr[R].
  165. //      Parameters:
  166. //        - arr : the input vector of long long integers (0-indexed).
  167. //        - queries : a vector of Query structs.
  168. //      Returns:
  169. //        - a vector<long long> where answer[i] is the sum for the i-th query.
  170. //      Time complexity: O((N + Q) * sqrt(N)).
  171. //      Constraint: none, but ensure sums fit in long long.
  172. //      Notes: This is just to show how easy it is to change the "add/remove"
  173. //             logic. You can adapt this pattern for many other problems.
  174. vector<long long> moSumRange(const vector<long long>& arr, const vector<Query>& queries) {
  175.     int n = arr.size();
  176.     int q = queries.size();
  177.     int blockSize = getMoBlockSize(n, q);
  178.  
  179.     vector<Query> sortedQueries = queries;
  180.     sort(sortedQueries.begin(), sortedQueries.end(),
  181.          [&](const Query& a, const Query& b) {
  182.              return moComparator(a, b, blockSize);
  183.          });
  184.  
  185.     vector<long long> ans(q, 0);
  186.     long long currentSum = 0;
  187.     int curL = 0, curR = -1;
  188.  
  189.     auto add = [&](int pos) { currentSum += arr[pos]; };
  190.     auto remove = [&](int pos) { currentSum -= arr[pos]; };
  191.  
  192.     for (const Query& qry : sortedQueries) {
  193.         while (curL > qry.l) add(--curL);
  194.         while (curR < qry.r) add(++curR);
  195.         while (curL < qry.l) remove(curL++);
  196.         while (curR > qry.r) remove(curR--);
  197.         ans[qry.idx] = currentSum;
  198.     }
  199.     return ans;
  200. }
  201.  
  202. // 2.3) Find the maximum frequency (mode count) in each query range.
  203. //      Purpose:
  204. //        - Given an array, for each query [L, R], find the highest
  205. //          frequency of any element in that range.
  206. //          Example: [1, 2, 2, 3] -> max frequency is 2 (because 2 appears twice).
  207. //      Parameters:
  208. //        - arr : the input vector of integers (0-indexed).
  209. //        - queries : a vector of Query structs.
  210. //      Returns:
  211. //        - a vector<int> where answer[i] is the max frequency for the i-th query.
  212. //      Time complexity: O((N + Q) * sqrt(N)).
  213. //      Constraint:
  214. //        - Values in 'arr' should be within a reasonable range (or compressed).
  215. //      Notes:
  216. //        - This requires two arrays: 'freq' to count each value, and
  217. //          'freqOfFreq' to count how many values have a specific frequency.
  218. //        - The 'maxFreq' variable is updated dynamically.
  219. vector<int> moMaxFrequency(const vector<int>& arr, const vector<Query>& queries) {
  220.     int n = arr.size();
  221.     int q = queries.size();
  222.     int blockSize = getMoBlockSize(n, q);
  223.  
  224.     vector<Query> sortedQueries = queries;
  225.     sort(sortedQueries.begin(), sortedQueries.end(),
  226.          [&](const Query& a, const Query& b) {
  227.              return moComparator(a, b, blockSize);
  228.          });
  229.  
  230.     vector<int> ans(q, 0);
  231.     vector<int> freq(200005, 0);       // Count of each value
  232.     vector<int> freqOfFreq(200005, 0); // Count of frequencies
  233.     int maxFreq = 0;
  234.     int curL = 0, curR = -1;
  235.  
  236.     auto add = [&](int pos) {
  237.         int val = arr[pos];
  238.         // Remove old frequency count from freqOfFreq
  239.         freqOfFreq[freq[val]]--;
  240.         // Increase frequency
  241.         freq[val]++;
  242.         // Add new frequency count
  243.         freqOfFreq[freq[val]]++;
  244.         maxFreq = max(maxFreq, freq[val]);
  245.     };
  246.  
  247.     auto remove = [&](int pos) {
  248.         int val = arr[pos];
  249.         freqOfFreq[freq[val]]--;
  250.         if (freq[val] == maxFreq && freqOfFreq[freq[val]] == 0) {
  251.             // If no value has 'maxFreq' anymore, we need to decrease maxFreq.
  252.             maxFreq--;
  253.         }
  254.         freq[val]--;
  255.         freqOfFreq[freq[val]]++;
  256.     };
  257.  
  258.     for (const Query& qry : sortedQueries) {
  259.         while (curL > qry.l) add(--curL);
  260.         while (curR < qry.r) add(++curR);
  261.         while (curL < qry.l) remove(curL++);
  262.         while (curR > qry.r) remove(curR--);
  263.         ans[qry.idx] = maxFreq;
  264.     }
  265.     return ans;
  266. }
  267.  
  268. // ===================================================================
  269. // 3) Mo's Algorithm with Point Updates (Mo with Updates)
  270. //    This handles queries that ask about a range, but the array can
  271. //    change between queries (point updates).
  272. // ===================================================================
  273.  
  274. // 3.1) Count distinct elements with updates.
  275. //      Purpose:
  276. //        - We have an array. Some queries ask for distinct elements in [L, R].
  277. //          Other queries ask to change the value at position 'pos' to 'newVal'.
  278. //          We must answer all range queries after applying updates in order.
  279. //      Parameters:
  280. //        - arr : the initial vector of integers (will be modified internally).
  281. //        - queries : a vector of QueryWithUpdate structs.
  282. //                    For Mo with updates, QueryWithUpdate must have 'l', 'r', 'idx', 'time'.
  283. //                    'time' is the number of updates that happened BEFORE this query.
  284. //        - updates : a vector of UpdateQuery structs (the changes to apply).
  285. //      Returns:
  286. //        - a vector<int> where answer[i] is the distinct count for the i-th
  287. //          query (ordered by original query index).
  288. //      Time complexity: O((N + Q) * N^(2/3)) which is faster than standard Mo
  289. //                       with updates. More precisely O(N^(2/3) * (N+Q)).
  290. //      Constraint:
  291. //        - The number of updates and queries can be up to ~1e5.
  292. //        - Values must be compressible.
  293. //      Notes:
  294. //        - This is also called "3D Mo" (L, R, Time).
  295. //        - The sorting order is: block of L, block of R, then Time.
  296. //        - To prepare the input: create a QueryWithUpdate for each range query.
  297. //          Set 'idx' to its order. Set 'l' to L, 'r' to R, and 'time' to the
  298. //          number of updates that have occurred before this query.
  299. struct QueryWithUpdate {
  300.     int l, r, idx, time; // time = number of updates before this query.
  301. };
  302.  
  303. vector<int> moDistinctWithUpdates(vector<int>& arr,
  304.                                   const vector<QueryWithUpdate>& queries,
  305.                                   const vector<UpdateQuery>& updates) {
  306.     int n = arr.size();
  307.     int q = queries.size();
  308.     int u = updates.size();
  309.  
  310.     int blockSize = pow(n, 2.0 / 3.0);
  311.     if (blockSize < 1) blockSize = 1;
  312.  
  313.     vector<QueryWithUpdate> sortedQueries = queries;
  314.     sort(sortedQueries.begin(), sortedQueries.end(),
  315.          [&](const QueryWithUpdate& a, const QueryWithUpdate& b) {
  316.              int blockL_a = a.l / blockSize;
  317.              int blockL_b = b.l / blockSize;
  318.              if (blockL_a != blockL_b) return blockL_a < blockL_b;
  319.  
  320.              int blockR_a = a.r / blockSize;
  321.              int blockR_b = b.r / blockSize;
  322.              if (blockR_a != blockR_b) return blockR_a < blockR_b;
  323.  
  324.              return a.time < b.time;
  325.          });
  326.  
  327.     vector<int> ans(q, 0);
  328.     vector<int> freq(200005, 0);
  329.     int distinctCount = 0;
  330.     int curL = 0, curR = -1, curTime = 0;
  331.  
  332.     auto add = [&](int pos) {
  333.         int val = arr[pos];
  334.         if (freq[val] == 0) distinctCount++;
  335.         freq[val]++;
  336.     };
  337.  
  338.     auto remove = [&](int pos) {
  339.         int val = arr[pos];
  340.         freq[val]--;
  341.         if (freq[val] == 0) distinctCount--;
  342.     };
  343.  
  344.     // Applies an update (forward or backward in time)
  345.     auto applyUpdate = [&](int time, bool forward) {
  346.         if (forward) {
  347.             // Apply updates[time] to arr
  348.             int pos = updates[time].pos;
  349.             int oldVal = updates[time].oldVal;
  350.             int newVal = updates[time].newVal;
  351.  
  352.             if (curL <= pos && pos <= curR) {
  353.                 // If this position is inside the current range, adjust counts
  354.                 freq[oldVal]--;
  355.                 if (freq[oldVal] == 0) distinctCount--;
  356.                 if (freq[newVal] == 0) distinctCount++;
  357.                 freq[newVal]++;
  358.             }
  359.             arr[pos] = newVal;
  360.         } else {
  361.             // Revert updates[time]
  362.             int pos = updates[time].pos;
  363.             int oldVal = updates[time].oldVal;
  364.             int newVal = updates[time].newVal; // current value
  365.  
  366.             if (curL <= pos && pos <= curR) {
  367.                 freq[newVal]--;
  368.                 if (freq[newVal] == 0) distinctCount--;
  369.                 if (freq[oldVal] == 0) distinctCount++;
  370.                 freq[oldVal]++;
  371.             }
  372.             arr[pos] = oldVal;
  373.         }
  374.     };
  375.  
  376.     for (const QueryWithUpdate& qry : sortedQueries) {
  377.         // Adjust L, R pointers
  378.         while (curL > qry.l) add(--curL);
  379.         while (curR < qry.r) add(++curR);
  380.         while (curL < qry.l) remove(curL++);
  381.         while (curR > qry.r) remove(curR--);
  382.  
  383.         // Adjust Time pointers
  384.         while (curTime < qry.time) {
  385.             applyUpdate(curTime, true);
  386.             curTime++;
  387.         }
  388.         while (curTime > qry.time) {
  389.             curTime--;
  390.             applyUpdate(curTime, false);
  391.         }
  392.  
  393.         ans[qry.idx] = distinctCount;
  394.     }
  395.     return ans;
  396. }
  397. // ===================================================================
  398.  
  399. // ===================================================================
  400. // 4) Mo's Algorithm on Trees
  401. //    This answers path queries on a tree.
  402. //    Example: "Count distinct values on the path from node U to node V".
  403. // ===================================================================
  404.  
  405. // 4.1) Flatten a tree into an Euler tour array for Mo's algorithm.
  406. //      Purpose:
  407. //        - To use Mo's algorithm on a tree, we first flatten it into
  408. //          an array of length 2*N.
  409. //        - This helper function builds that array and provides the
  410. //          entry (tin) and exit (tout) times for each node.
  411. //      Parameters:
  412. //        - adj : adjacency list of the tree (vector<vector<int>>).
  413. //        - root : the root node of the tree (usually 0).
  414. //      Returns:
  415. //        - a tuple containing:
  416. //            euler : vector<int> of length 2*N (node labels).
  417. //            tin : vector<int> where tin[u] is the first occurrence index.
  418. //            tout : vector<int> where tout[u] is the second occurrence index.
  419. //      Time complexity: O(N)
  420. //      Constraint: The graph must be a tree (no cycles).
  421. //      Notes:
  422. //        - We add a node to 'euler' when we enter it, and again when we exit.
  423. tuple<vector<int>, vector<int>, vector<int>> flattenTreeForMo(const vector<vector<int>>& adj, int root) {
  424.     int n = adj.size();
  425.     vector<int> euler;
  426.     euler.reserve(2 * n);
  427.     vector<int> tin(n, 0), tout(n, 0);
  428.     int timer = 0;
  429.  
  430.     function<void(int, int)> dfs = [&](int u, int p) {
  431.         tin[u] = timer++;
  432.         euler.push_back(u);
  433.         for (int v : adj[u]) {
  434.             if (v == p) continue;
  435.             dfs(v, u);
  436.         }
  437.         tout[u] = timer++;
  438.         euler.push_back(u);
  439.     };
  440.  
  441.     dfs(root, -1);
  442.     return {euler, tin, tout};
  443. }
  444.  
  445. // 4.2) Answer path queries on a tree (e.g., distinct nodes on path).
  446. //      Purpose:
  447. //        - Given a tree, answer queries asking for the number of distinct
  448. //          values on the path between node 'U' and node 'V'.
  449. //      Parameters:
  450. //        - nodeValues : the value of each node (vector<int> of size N).
  451. //        - euler : the flattened array from flattenTreeForMo().
  452. //        - tin, tout : the tin/tout arrays from flattenTreeForMo().
  453. //        - pathQueries : a vector of pairs (u, v) representing path queries.
  454. //        - getLCA : a function that returns the LCA of two nodes.
  455. //                   (You must provide one, e.g., binary lifting).
  456. //      Returns:
  457. //        - a vector<int> where answer[i] is the distinct count on the path.
  458. //      Time complexity: O((N + Q) * sqrt(N) + Q * log(N)) for LCA.
  459. //      Constraint:
  460. //        - Node values must be compressible.
  461. //        - The LCA function must be correct.
  462. //      Notes (IMPORTANT on how to use this):
  463. //        - Step 1: Run flattenTreeForMo() to get 'euler', 'tin', 'tout'.
  464. //        - Step 2: For each path query (u, v), the function builds a range
  465. //          on the Euler array and handles LCA inclusion automatically.
  466. vector<int> moOnTreeDistinct(const vector<int>& nodeValues,
  467.                              const vector<int>& euler,
  468.                              const vector<int>& tin,
  469.                              const vector<int>& tout,
  470.                              const vector<pair<int,int>>& pathQueries,
  471.                              function<int(int,int)> getLCA) {
  472.     int n = nodeValues.size();
  473.     int q = pathQueries.size();
  474.     int m = euler.size(); // = 2*n
  475.  
  476.     // Build regular queries for Mo on the Euler array
  477.     vector<Query> queries(q);
  478.     vector<int> lcaNode(q);
  479.     vector<int> leftNode(q);      // the node with smaller tin after swapping
  480.     vector<bool> includeLca(q);   // whether the LCA is already included in the range
  481.  
  482.     for (int i = 0; i < q; i++) {
  483.         int u = pathQueries[i].first;
  484.         int v = pathQueries[i].second;
  485.         if (tin[u] > tin[v]) swap(u, v);
  486.         int w = getLCA(u, v);
  487.         lcaNode[i] = w;
  488.         leftNode[i] = u;
  489.         includeLca[i] = (w == u);
  490.  
  491.         if (includeLca[i]) {
  492.             queries[i] = {tin[u], tin[v], i};
  493.         } else {
  494.             queries[i] = {tout[u], tin[v], i};
  495.         }
  496.     }
  497.  
  498.     int blockSize = getMoBlockSize(m, q);
  499.     vector<Query> sortedQueries = queries;
  500.     sort(sortedQueries.begin(), sortedQueries.end(),
  501.          [&](const Query& a, const Query& b) {
  502.              return moComparator(a, b, blockSize);
  503.          });
  504.  
  505.     vector<int> ans(q, 0);
  506.     vector<int> freq(200005, 0); // Assumes node values are < 200k
  507.     vector<bool> vis(n, false);
  508.     int distinctCount = 0;
  509.     int curL = 0, curR = -1;
  510.  
  511.     auto toggle = [&](int node) {
  512.         int val = nodeValues[node];
  513.         if (vis[node]) {
  514.             // Remove
  515.             freq[val]--;
  516.             if (freq[val] == 0) distinctCount--;
  517.         } else {
  518.             // Add
  519.             if (freq[val] == 0) distinctCount++;
  520.             freq[val]++;
  521.         }
  522.         vis[node] = !vis[node];
  523.     };
  524.  
  525.     for (const Query& qry : sortedQueries) {
  526.         while (curL > qry.l) {
  527.             curL--;
  528.             toggle(euler[curL]);
  529.         }
  530.         while (curR < qry.r) {
  531.             curR++;
  532.             toggle(euler[curR]);
  533.         }
  534.         while (curL < qry.l) {
  535.             toggle(euler[curL]);
  536.             curL++;
  537.         }
  538.         while (curR > qry.r) {
  539.             toggle(euler[curR]);
  540.             curR--;
  541.         }
  542.  
  543.         // Add LCA if it is not already included in the range
  544.         if (!includeLca[qry.idx]) {
  545.             int lca = lcaNode[qry.idx];
  546.             int val = nodeValues[lca];
  547.             if (freq[val] == 0) distinctCount++;
  548.             freq[val]++;
  549.         }
  550.  
  551.         ans[qry.idx] = distinctCount;
  552.  
  553.         // Remove the temporary LCA addition
  554.         if (!includeLca[qry.idx]) {
  555.             int lca = lcaNode[qry.idx];
  556.             int val = nodeValues[lca];
  557.             freq[val]--;
  558.             if (freq[val] == 0) distinctCount--;
  559.         }
  560.     }
  561.  
  562.     return ans;
  563. }
  564.  
  565. // ===================================================================
  566. // 5) Advanced Tricks & Helpers
  567. // ===================================================================
  568.  
  569. // 5.1) Hilbert Order Sorting (an alternative to block sorting).
  570. //      Purpose:
  571. //        - Hilbert order is a way to sort queries that often reduces
  572. //          pointer movement even more than the standard sqrt block sort.
  573. //      Parameters:
  574. //        - x, y : the L and R of the query.
  575. //        - pow2 : a power of 2 greater than the maximum coordinate (N).
  576. //        - rot : rotation (usually 0).
  577. //      Returns:
  578. //        - a 64-bit integer representing the Hilbert order key.
  579. //      Time complexity: O(log N)
  580. //      Notes:
  581. //        - You can use this as a comparator instead of moComparator.
  582. //          If you use this, you don't need the block size.
  583. //        - It is considered an "advanced trick" and is useful for
  584. //          performance-critical problems.
  585. long long hilbertOrder(int x, int y, int pow2, int rot) {
  586.     if (pow2 == 0) return 0;
  587.     int hpow = pow2 >> 1;
  588.     int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
  589.     seg = (seg + rot) & 3;
  590.     static const int rotateDelta[4] = {3, 0, 0, 1};
  591.     int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
  592.     int nrot = (rot + rotateDelta[seg]) & 3;
  593.     long long subSquareSize = 1LL << (2 * (pow2 - 1));
  594.     long long ans = seg * subSquareSize;
  595.     long long add = hilbertOrder(nx, ny, hpow, nrot);
  596.     ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
  597.     return ans;
  598. }
  599.  
  600. // ===================================================================
  601. // 6) Extra Utility: Mex (Minimum Excluded) in a range using Mo.
  602. //    Finds the smallest non-negative integer missing from a range.
  603. // ===================================================================
  604.  
  605. // 6.1) Find the Mex (Minimum EXcluded) for each query range.
  606. //      Purpose:
  607. //        - For each query [L, R], find the smallest non-negative integer
  608. //          that does NOT appear in arr[L..R].
  609. //        - Example: [0, 1, 3] -> Mex is 2. [1, 2, 3] -> Mex is 0.
  610. //      Parameters:
  611. //        - arr : vector of non-negative integers (0-indexed).
  612. //        - queries : vector of Query structs.
  613. //      Returns:
  614. //        - vector<int> where ans[i] is the Mex for the i-th query.
  615. //      Time complexity: O((N + Q) * sqrt(N)).
  616. //      Constraint:
  617. //        - arr values must be >= 0.
  618. //      Notes:
  619. //        - Mex is at most N (size of array).
  620. //        - We maintain a 'freq' array and a block decomposition on values
  621. //          to answer Mex in O(sqrt(N)) per query.
  622. vector<int> moMex(const vector<int>& arr, const vector<Query>& queries) {
  623.     int n = arr.size();
  624.     int q = queries.size();
  625.     int blockSize = getMoBlockSize(n, q);
  626.  
  627.     vector<Query> sortedQueries = queries;
  628.     sort(sortedQueries.begin(), sortedQueries.end(),
  629.          [&](const Query& a, const Query& b) {
  630.              return moComparator(a, b, blockSize);
  631.          });
  632.  
  633.     vector<int> ans(q, 0);
  634.     // freq for values. Mex can be up to n (since only n elements).
  635.     vector<int> freq(n + 2, 0);
  636.     // Decomposition on the values to find Mex in O(sqrt(N)).
  637.     int valBlockSize = max(1, (int)sqrt(n) + 1);
  638.     vector<int> valBlockFreq((n + 2) / valBlockSize + 2, 0);
  639.  
  640.     auto add = [&](int pos) {
  641.         int val = arr[pos];
  642.         if (val > n) return; // ignore values bigger than n, they don't affect Mex.
  643.         if (freq[val] == 0) valBlockFreq[val / valBlockSize]++;
  644.         freq[val]++;
  645.     };
  646.  
  647.     auto remove = [&](int pos) {
  648.         int val = arr[pos];
  649.         if (val > n) return;
  650.         freq[val]--;
  651.         if (freq[val] == 0) valBlockFreq[val / valBlockSize]--;
  652.     };
  653.  
  654.     auto getMex = [&]() {
  655.         // Find the first block that has a missing number.
  656.         for (int b = 0; b < (int)valBlockFreq.size(); b++) {
  657.             if (valBlockFreq[b] < valBlockSize) {
  658.                 // Inside this block, find the missing number.
  659.                 int start = b * valBlockSize;
  660.                 for (int i = start; i < start + valBlockSize; i++) {
  661.                     if (freq[i] == 0) return i;
  662.                 }
  663.             }
  664.         }
  665.         return n + 1; // Should never happen.
  666.     };
  667.  
  668.     int curL = 0, curR = -1;
  669.     for (const Query& qry : sortedQueries) {
  670.         while (curL > qry.l) add(--curL);
  671.         while (curR < qry.r) add(++curR);
  672.         while (curL < qry.l) remove(curL++);
  673.         while (curR > qry.r) remove(curR--);
  674.         ans[qry.idx] = getMex();
  675.     }
  676.     return ans;
  677. }
  678.  
  679. // ===================================================================
  680. // 7) Important Note on Coordinate Compression
  681. //    If your array contains large numbers (e.g., up to 1e9), you must
  682. //    compress them before using functions that rely on a frequency array.
  683. //    Here is a helper to do that.
  684. // ===================================================================
  685.  
  686. // 7.1) Compress an array of values to 0..M-1.
  687. //      Purpose:
  688. //        - Maps large values to small indices so we can use frequency arrays.
  689. //      Parameters:
  690. //        - arr : vector of integers (will be copied and modified).
  691. //      Returns:
  692. //        - a new vector where each value is replaced by its rank (0-based).
  693. //      Time complexity: O(N log N)
  694. //      Constraint: none.
  695. //      Notes: This preserves the relative order. Equal values get the same rank.
  696. vector<int> compressArray(const vector<int>& arr) {
  697.     vector<int> sorted = arr;
  698.     sort(sorted.begin(), sorted.end());
  699.     sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
  700.     vector<int> res(arr.size());
  701.     for (int i = 0; i < (int)arr.size(); i++) {
  702.         res[i] = lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin();
  703.     }
  704.     return res;
  705. }
  706.  
  707. // ===================================================================
  708. // main() with example usage (you can ignore this part)
  709. // ===================================================================
  710.  
  711. int main() {
  712.     ios::sync_with_stdio(false);
  713.     cin.tie(nullptr);
  714.  
  715.     // Example 1: Distinct elements in range
  716.     vector<int> arr = {1, 2, 1, 3, 2, 4};
  717.     vector<Query> queries = {
  718.         {0, 3, 0}, // [1,2,1,3] -> distinct = 3
  719.         {1, 4, 1}, // [2,1,3,2] -> distinct = 3
  720.         {2, 5, 2}  // [1,3,2,4] -> distinct = 4
  721.     };
  722.     vector<int> distinctAns = moDistinctElements(arr, queries);
  723.     for (int i = 0; i < (int)distinctAns.size(); i++) {
  724.         cout << "Query " << i << ": " << distinctAns[i] << "\n";
  725.     }
  726.  
  727.     // Example 2: Mex in range
  728.     vector<int> arr2 = {0, 1, 2, 3, 0, 1};
  729.     vector<Query> queries2 = {
  730.         {0, 2, 0}, // [0,1,2] -> Mex = 3
  731.         {1, 3, 1}, // [1,2,3] -> Mex = 0
  732.         {2, 5, 2}  // [2,3,0,1] -> Mex = 4
  733.     };
  734.     vector<int> mexAns = moMex(arr2, queries2);
  735.     cout << "\nMex results:\n";
  736.     for (int i = 0; i < (int)mexAns.size(); i++) {
  737.         cout << "Query " << i << ": " << mexAns[i] << "\n";
  738.     }
  739.  
  740.     // Example 3: Max Frequency
  741.     vector<int> arr3 = {1, 2, 2, 3, 3, 3, 4};
  742.     vector<Query> queries3 = {
  743.         {0, 6, 0},
  744.         {1, 3, 1},
  745.         {2, 4, 2}
  746.     };
  747.     vector<int> freqAns = moMaxFrequency(arr3, queries3);
  748.     cout << "\nMax Frequency:\n";
  749.     for (int x : freqAns) cout << x << " ";
  750.     cout << "\n";
  751.  
  752.     return 0;
  753. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Query 0: 3
Query 1: 3
Query 2: 4

Mex results:
Query 0: 3
Query 1: 0
Query 2: 4

Max Frequency:
3 2 2
https://ideone.com/R1i4C9
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!