fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. // ===================================================================
  6. // This file provides a collection of functions implementing Mo's Algorithm
  7. // with updates (also known as Mo's algorithm with modifications).
  8. // It is designed for competitive programming (ECPC / ACPC). Each function
  9. // is ready to be used as a black box.
  10. //
  11. // What is Mo's Algorithm?
  12. //   It is an offline technique that answers range queries (e.g. subarray
  13. //   queries) by dividing the queries into blocks and sorting them cleverly.
  14. //   This minimises the movement of two pointers (L and R) across the array.
  15. //
  16. // What are "updates"?
  17. //   An update is a point modification that changes the value of one element
  18. //   of the array at a specific position. In Mo with updates, we also keep a
  19. //   third pointer "time" that moves forward/backward through the list of
  20. //   updates. The algorithm handles queries that are interleaved with updates.
  21. //
  22. // Important terms:
  23. //   - Query: a request to compute something on a subarray [L, R] at a given
  24. //     "time" (i.e. after a certain number of updates have been applied).
  25. //   - Update: a structure {pos, oldVal, newVal} that changes arr[pos] from
  26. //     oldVal to newVal.
  27. //   - Time: the number of updates that have been performed before a query.
  28. //   - Block size: the size of the blocks used for sorting. For Mo with
  29. //     updates, a typical choice is N^(2/3) (where N is the array size).
  30. //   - Coordinate compression: mapping large values to a smaller range to
  31. //     use a frequency array efficiently.
  32. //
  33. // Time complexity: O((N + Q) * N^(2/3)) approximately, where N is the array
  34. // size and Q is the number of queries. With optimisations it can be fast
  35. // enough for typical constraints (N, Q <= 1e5).
  36. // ===================================================================
  37.  
  38. // ===================================================================
  39. // 1) Data Structures for Mo with Updates
  40. // ===================================================================
  41.  
  42. // Represents one point update:
  43. //   pos    : index in the array (0-based)
  44. //   oldVal : value before the update
  45. //   newVal : value after the update
  46. struct Update {
  47.     int pos;
  48.     int oldVal;
  49.     int newVal;
  50. };
  51.  
  52. // Represents one query:
  53. //   L, R  : inclusive range [L, R] (0‑based)
  54. //   idx   : original index of the query (used to store the answer)
  55. //   time  : number of updates that must be applied before answering this query
  56. //          (i.e. the index in the updates list up to which we need to apply)
  57. struct Query {
  58.     int L, R;
  59.     int idx;
  60.     int time;
  61. };
  62.  
  63. // Global block size used for sorting queries.
  64. // It should be set to pow(N, 2.0/3.0) + 1 before sorting.
  65. int MO_BLOCK;
  66.  
  67. // Comparator used to sort queries for Mo's algorithm with updates.
  68. // Sorts by block of L, then block of R (with alternating direction),
  69. // then time (also alternating for speed).
  70. bool moComparator(const Query& a, const Query& b) {
  71.     int blockL_a = a.L / MO_BLOCK;
  72.     int blockL_b = b.L / MO_BLOCK;
  73.     if (blockL_a != blockL_b) return blockL_a < blockL_b;
  74.  
  75.     int blockR_a = a.R / MO_BLOCK;
  76.     int blockR_b = b.R / MO_BLOCK;
  77.     if (blockR_a != blockR_b) {
  78.         // alternate direction of R blocks to reduce movement
  79.         return (blockR_a & 1) ? blockR_a > blockR_b : blockR_a < blockR_b;
  80.     }
  81.  
  82.     // alternate direction of time as well
  83.     return (blockR_a & 1) ? a.time > b.time : a.time < b.time;
  84. }
  85.  
  86. // ===================================================================
  87. // 2) Helper Functions for Updates and Compression
  88. // ===================================================================
  89.  
  90. // Applies a single update to the array (without changing any query state).
  91. // This is used to prepare the array before building queries, or to
  92. // revert the array after we finish.
  93. void applyUpdateToArray(vector<int>& arr, const Update& up) {
  94.     arr[up.pos] = up.newVal;
  95. }
  96.  
  97. // Given a list of changes (pos, newVal) in chronological order, this
  98. // function builds a vector of Update structures and fills the oldVal
  99. // automatically from the current array state. It also modifies the array
  100. // to the final state (applies all changes).
  101. //
  102. // Example:
  103. //   vector<pair<int,int>> changes = {{0, 5}, {2, 10}};
  104. //   vector<Update> updates = prepareUpdates(arr, changes);
  105. //   // now arr has been updated, and updates[0].oldVal is the original arr[0]
  106. vector<Update> prepareUpdates(vector<int>& arr, const vector<pair<int,int>>& changes) {
  107.     vector<Update> updates;
  108.     for (auto [pos, newVal] : changes) {
  109.         updates.push_back({pos, arr[pos], newVal});
  110.         arr[pos] = newVal;
  111.     }
  112.     return updates;
  113. }
  114.  
  115. // Coordinate compression: maps all values that appear in the array and
  116. // in the updates to a smaller set of integers [0 .. M-1]. This is useful
  117. // when values are large, because we can use a vector<int> as frequency array.
  118. // This function modifies arr and updates in place.
  119. void compressArray(vector<int>& arr, vector<Update>& updates) {
  120.     vector<int> vals = arr;
  121.     for (auto& u : updates) {
  122.         vals.push_back(u.oldVal);
  123.         vals.push_back(u.newVal);
  124.     }
  125.     sort(vals.begin(), vals.end());
  126.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  127.  
  128.     for (int& x : arr) {
  129.         x = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
  130.     }
  131.     for (auto& u : updates) {
  132.         u.oldVal = lower_bound(vals.begin(), vals.end(), u.oldVal) - vals.begin();
  133.         u.newVal = lower_bound(vals.begin(), vals.end(), u.newVal) - vals.begin();
  134.     }
  135. }
  136.  
  137. // ===================================================================
  138. // 3) Ready‑Made Functions for Common Query Types
  139. //    Each function is self‑contained and returns a vector of answers.
  140. //    They all assume that the queries vector has the correct idx and time.
  141. //    If values are large, call compressArray() before calling these functions.
  142. // ===================================================================
  143.  
  144. // -------------------------------------------------------------------
  145. // 4.1) Count distinct elements in each query range [L, R] with updates.
  146. //      Purpose: For each query, returns the number of different values
  147. //               that appear in the subarray arr[L..R] at that time.
  148. //      Parameters:
  149. //        - arr: vector of integers (passed by value; the function modifies it)
  150. //        - updates: vector of Update structures in chronological order
  151. //        - queries: vector of Query structures (must be filled with L,R,idx,time)
  152. //      Returns:
  153. //        - vector<int> answers, where answers[i] = distinct count for query i.
  154. //      Time complexity: O((N+Q) * N^(2/3)) approximately.
  155. //      Constraints:
  156. //        - arr values and update values should be compressed (small integers)
  157. //          or a large frequency array may be used (not recommended).
  158. //      Notes:
  159. //        - The function sorts the queries internally, so the order of queries
  160. //          in the input vector is not preserved.
  161. //        - The array is modified during processing but restored to the final
  162. //          state (all updates applied) after finishing.
  163. // -------------------------------------------------------------------
  164. vector<int> distinctWithUpdates(vector<int> arr, const vector<Update>& updates, vector<Query> queries) {
  165.     int n = (int)arr.size();
  166.     int q = (int)queries.size();
  167.     vector<int> ans(q);
  168.  
  169.     // Determine the maximum value to size the frequency array.
  170.     // If values are not compressed, this could be huge. Use compressArray first.
  171.     int maxVal = 0;
  172.     for (int x : arr) maxVal = max(maxVal, x);
  173.     for (auto& u : updates) maxVal = max(maxVal, max(u.oldVal, u.newVal));
  174.     vector<int> freq(maxVal + 1, 0);
  175.  
  176.     int curL = 0, curR = -1;          // current window [curL, curR]
  177.     int curTime = 0;                  // number of applied updates
  178.     int distinct = 0;                 // current distinct count
  179.  
  180.     auto add = [&](int idx) {
  181.         int val = arr[idx];
  182.         if (freq[val] == 0) distinct++;
  183.         freq[val]++;
  184.     };
  185.  
  186.     auto remove = [&](int idx) {
  187.         int val = arr[idx];
  188.         freq[val]--;
  189.         if (freq[val] == 0) distinct--;
  190.     };
  191.  
  192.     // Apply or revert one update (forward == true => apply, false => revert)
  193.     auto apply = [&](const Update& up, bool forward) {
  194.         int pos = up.pos;
  195.         int oldVal = up.oldVal;
  196.         int newVal = up.newVal;
  197.         if (forward) {
  198.             // If the update position is inside the current window, we must
  199.             // update the frequency structure before changing the array.
  200.             if (curL <= pos && pos <= curR) {
  201.                 // remove old value
  202.                 freq[oldVal]--;
  203.                 if (freq[oldVal] == 0) distinct--;
  204.                 // add new value
  205.                 if (freq[newVal] == 0) distinct++;
  206.                 freq[newVal]++;
  207.             }
  208.             arr[pos] = newVal;
  209.         } else {
  210.             // revert: undo the update
  211.             if (curL <= pos && pos <= curR) {
  212.                 // remove new value
  213.                 freq[newVal]--;
  214.                 if (freq[newVal] == 0) distinct--;
  215.                 // add old value
  216.                 if (freq[oldVal] == 0) distinct++;
  217.                 freq[oldVal]++;
  218.             }
  219.             arr[pos] = oldVal;
  220.         }
  221.     };
  222.  
  223.     // Set block size and sort queries
  224.     MO_BLOCK = (int)pow(n, 2.0/3.0) + 1;
  225.     sort(queries.begin(), queries.end(), moComparator);
  226.  
  227.     // Process queries
  228.     for (const Query& qry : queries) {
  229.         // Move time forward/backward
  230.         while (curTime < qry.time) {
  231.             apply(updates[curTime], true);
  232.             curTime++;
  233.         }
  234.         while (curTime > qry.time) {
  235.             curTime--;
  236.             apply(updates[curTime], false);
  237.         }
  238.         // Move L and R pointers
  239.         while (curL > qry.L) add(--curL);
  240.         while (curR < qry.R) add(++curR);
  241.         while (curL < qry.L) remove(curL++);
  242.         while (curR > qry.R) remove(curR--);
  243.         ans[qry.idx] = distinct;
  244.     }
  245.  
  246.     return ans;
  247. }
  248.  
  249. // -------------------------------------------------------------------
  250. // 4.2) Sum of elements in each query range [L, R] with updates.
  251. //      Purpose: Returns the sum of arr[i] for i in [L, R] at the query time.
  252. //      Parameters: same as distinctWithUpdates.
  253. //      Returns: vector<long long> answers (sums may overflow int).
  254. //      Time complexity: O((N+Q) * N^(2/3)).
  255. //      Constraints: same as above.
  256. //      Notes: No compression needed for sums, but values may be large.
  257. // -------------------------------------------------------------------
  258. vector<ll> sumWithUpdates(vector<int> arr, const vector<Update>& updates, vector<Query> queries) {
  259.     int n = (int)arr.size();
  260.     int q = (int)queries.size();
  261.     vector<ll> ans(q);
  262.     int curL = 0, curR = -1, curTime = 0;
  263.     ll sum = 0;
  264.  
  265.     auto add = [&](int idx) { sum += arr[idx]; };
  266.     auto remove = [&](int idx) { sum -= arr[idx]; };
  267.  
  268.     auto apply = [&](const Update& up, bool forward) {
  269.         int pos = up.pos;
  270.         int oldVal = up.oldVal;
  271.         int newVal = up.newVal;
  272.         if (forward) {
  273.             if (curL <= pos && pos <= curR) {
  274.                 sum -= oldVal;
  275.                 sum += newVal;
  276.             }
  277.             arr[pos] = newVal;
  278.         } else {
  279.             if (curL <= pos && pos <= curR) {
  280.                 sum -= newVal;
  281.                 sum += oldVal;
  282.             }
  283.             arr[pos] = oldVal;
  284.         }
  285.     };
  286.  
  287.     MO_BLOCK = (int)pow(n, 2.0/3.0) + 1;
  288.     sort(queries.begin(), queries.end(), moComparator);
  289.  
  290.     for (const Query& qry : queries) {
  291.         while (curTime < qry.time) apply(updates[curTime++], true);
  292.         while (curTime > qry.time) apply(updates[--curTime], false);
  293.         while (curL > qry.L) add(--curL);
  294.         while (curR < qry.R) add(++curR);
  295.         while (curL < qry.L) remove(curL++);
  296.         while (curR > qry.R) remove(curR--);
  297.         ans[qry.idx] = sum;
  298.     }
  299.     return ans;
  300. }
  301.  
  302. // -------------------------------------------------------------------
  303. // 4.3) Sum of squares of frequencies in each query range.
  304. //      Purpose: For each query, compute sum_{v} freq[v]^2, where freq[v]
  305. //               is the number of occurrences of value v in the subarray.
  306. //               This is useful for counting equal pairs (see 4.5).
  307. //      Parameters: same as distinctWithUpdates.
  308. //      Returns: vector<long long> answers.
  309. //      Time complexity: O((N+Q) * N^(2/3)).
  310. //      Notes: Values should be compressed so that freq array is small.
  311. // -------------------------------------------------------------------
  312. vector<ll> sumSqFreqWithUpdates(vector<int> arr, const vector<Update>& updates, vector<Query> queries) {
  313.     int n = (int)arr.size();
  314.     int q = (int)queries.size();
  315.     vector<ll> ans(q);
  316.  
  317.     int maxVal = 0;
  318.     for (int x : arr) maxVal = max(maxVal, x);
  319.     for (auto& u : updates) maxVal = max(maxVal, max(u.oldVal, u.newVal));
  320.     vector<int> freq(maxVal + 1, 0);
  321.  
  322.     int curL = 0, curR = -1, curTime = 0;
  323.     ll sumSq = 0;
  324.  
  325.     auto add = [&](int idx) {
  326.         int val = arr[idx];
  327.         sumSq += 2LL * freq[val] + 1;   // (f+1)^2 - f^2 = 2f+1
  328.         freq[val]++;
  329.     };
  330.  
  331.     auto remove = [&](int idx) {
  332.         int val = arr[idx];
  333.         freq[val]--;
  334.         sumSq -= 2LL * freq[val] + 1;   // f^2 - (f-1)^2 = 2f-1, but after decrement
  335.     };
  336.  
  337.     auto apply = [&](const Update& up, bool forward) {
  338.         int pos = up.pos;
  339.         int oldVal = up.oldVal;
  340.         int newVal = up.newVal;
  341.         if (forward) {
  342.             if (curL <= pos && pos <= curR) {
  343.                 // remove old, add new
  344.                 freq[oldVal]--;
  345.                 sumSq -= 2LL * freq[oldVal] + 1;
  346.                 sumSq += 2LL * freq[newVal] + 1;
  347.                 freq[newVal]++;
  348.             }
  349.             arr[pos] = newVal;
  350.         } else {
  351.             if (curL <= pos && pos <= curR) {
  352.                 // remove new, add old
  353.                 freq[newVal]--;
  354.                 sumSq -= 2LL * freq[newVal] + 1;
  355.                 sumSq += 2LL * freq[oldVal] + 1;
  356.                 freq[oldVal]++;
  357.             }
  358.             arr[pos] = oldVal;
  359.         }
  360.     };
  361.  
  362.     MO_BLOCK = (int)pow(n, 2.0/3.0) + 1;
  363.     sort(queries.begin(), queries.end(), moComparator);
  364.  
  365.     for (const Query& qry : queries) {
  366.         while (curTime < qry.time) apply(updates[curTime++], true);
  367.         while (curTime > qry.time) apply(updates[--curTime], false);
  368.         while (curL > qry.L) add(--curL);
  369.         while (curR < qry.R) add(++curR);
  370.         while (curL < qry.L) remove(curL++);
  371.         while (curR > qry.R) remove(curR--);
  372.         ans[qry.idx] = sumSq;
  373.     }
  374.     return ans;
  375. }
  376.  
  377. // -------------------------------------------------------------------
  378. // 4.4) Maximum frequency (mode frequency) in each query range with updates.
  379. //      Purpose: Returns the highest frequency among all values in the subarray.
  380. //      Parameters: same as distinctWithUpdates.
  381. //      Returns: vector<int> answers (maximum frequency).
  382. //      Time complexity: O((N+Q) * N^(2/3)).
  383. //      Notes: Uses an additional frequency‑of‑frequency array to maintain max.
  384. // -------------------------------------------------------------------
  385. vector<int> modeFreqWithUpdates(vector<int> arr, const vector<Update>& updates, vector<Query> queries) {
  386.     int n = (int)arr.size();
  387.     int q = (int)queries.size();
  388.     vector<int> ans(q);
  389.  
  390.     int maxVal = 0;
  391.     for (int x : arr) maxVal = max(maxVal, x);
  392.     for (auto& u : updates) maxVal = max(maxVal, max(u.oldVal, u.newVal));
  393.     vector<int> freq(maxVal + 1, 0);
  394.     vector<int> freqOfFreq(n + 1, 0); // freqOfFreq[f] = number of values with frequency f
  395.     int curL = 0, curR = -1, curTime = 0;
  396.     int maxFreq = 0;
  397.  
  398.     auto add = [&](int idx) {
  399.         int val = arr[idx];
  400.         int f = freq[val];
  401.         if (f > 0) freqOfFreq[f]--;
  402.         freq[val]++;
  403.         freqOfFreq[f + 1]++;
  404.         maxFreq = max(maxFreq, f + 1);
  405.     };
  406.  
  407.     auto remove = [&](int idx) {
  408.         int val = arr[idx];
  409.         int f = freq[val];
  410.         freqOfFreq[f]--;
  411.         if (f == maxFreq && freqOfFreq[f] == 0) {
  412.             // decrease maxFreq until there is at least one value with that frequency
  413.             while (maxFreq > 0 && freqOfFreq[maxFreq] == 0) maxFreq--;
  414.         }
  415.         freq[val]--;
  416.         freqOfFreq[f - 1]++;
  417.     };
  418.  
  419.     auto apply = [&](const Update& up, bool forward) {
  420.         int pos = up.pos;
  421.         int oldVal = up.oldVal;
  422.         int newVal = up.newVal;
  423.         if (forward) {
  424.             if (curL <= pos && pos <= curR) {
  425.                 // remove old
  426.                 int f = freq[oldVal];
  427.                 freqOfFreq[f]--;
  428.                 if (f == maxFreq && freqOfFreq[f] == 0) {
  429.                     while (maxFreq > 0 && freqOfFreq[maxFreq] == 0) maxFreq--;
  430.                 }
  431.                 freq[oldVal]--;
  432.                 freqOfFreq[f - 1]++;
  433.  
  434.                 // add new
  435.                 f = freq[newVal];
  436.                 if (f > 0) freqOfFreq[f]--;
  437.                 freq[newVal]++;
  438.                 freqOfFreq[f + 1]++;
  439.                 maxFreq = max(maxFreq, f + 1);
  440.             }
  441.             arr[pos] = newVal;
  442.         } else {
  443.             if (curL <= pos && pos <= curR) {
  444.                 // remove new
  445.                 int f = freq[newVal];
  446.                 freqOfFreq[f]--;
  447.                 if (f == maxFreq && freqOfFreq[f] == 0) {
  448.                     while (maxFreq > 0 && freqOfFreq[maxFreq] == 0) maxFreq--;
  449.                 }
  450.                 freq[newVal]--;
  451.                 freqOfFreq[f - 1]++;
  452.  
  453.                 // add old
  454.                 f = freq[oldVal];
  455.                 if (f > 0) freqOfFreq[f]--;
  456.                 freq[oldVal]++;
  457.                 freqOfFreq[f + 1]++;
  458.                 maxFreq = max(maxFreq, f + 1);
  459.             }
  460.             arr[pos] = oldVal;
  461.         }
  462.     };
  463.  
  464.     MO_BLOCK = (int)pow(n, 2.0/3.0) + 1;
  465.     sort(queries.begin(), queries.end(), moComparator);
  466.  
  467.     for (const Query& qry : queries) {
  468.         while (curTime < qry.time) apply(updates[curTime++], true);
  469.         while (curTime > qry.time) apply(updates[--curTime], false);
  470.         while (curL > qry.L) add(--curL);
  471.         while (curR < qry.R) add(++curR);
  472.         while (curL < qry.L) remove(curL++);
  473.         while (curR > qry.R) remove(curR--);
  474.         ans[qry.idx] = maxFreq;
  475.     }
  476.     return ans;
  477. }
  478.  
  479. // -------------------------------------------------------------------
  480. // 4.5) Number of equal pairs (i, j) with L <= i < j <= R in each query.
  481. //      Purpose: Counts unordered pairs of indices within the range that
  482. //               have equal values. This equals (sumSq - len) / 2.
  483. //      Parameters: same as distinctWithUpdates.
  484. //      Returns: vector<long long> answers (number of pairs).
  485. //      Time complexity: O((N+Q) * N^(2/3)).
  486. // -------------------------------------------------------------------
  487. vector<ll> countPairsEqualWithUpdates(vector<int> arr, const vector<Update>& updates, vector<Query> queries) {
  488.     int n = (int)arr.size();
  489.     int q = (int)queries.size();
  490.     vector<ll> ans(q);
  491.  
  492.     int maxVal = 0;
  493.     for (int x : arr) maxVal = max(maxVal, x);
  494.     for (auto& u : updates) maxVal = max(maxVal, max(u.oldVal, u.newVal));
  495.     vector<int> freq(maxVal + 1, 0);
  496.  
  497.     int curL = 0, curR = -1, curTime = 0;
  498.     ll sumSq = 0;
  499.  
  500.     auto add = [&](int idx) {
  501.         int val = arr[idx];
  502.         sumSq += 2LL * freq[val] + 1;
  503.         freq[val]++;
  504.     };
  505.     auto remove = [&](int idx) {
  506.         int val = arr[idx];
  507.         freq[val]--;
  508.         sumSq -= 2LL * freq[val] + 1;
  509.     };
  510.     auto apply = [&](const Update& up, bool forward) {
  511.         int pos = up.pos;
  512.         int oldVal = up.oldVal;
  513.         int newVal = up.newVal;
  514.         if (forward) {
  515.             if (curL <= pos && pos <= curR) {
  516.                 freq[oldVal]--;
  517.                 sumSq -= 2LL * freq[oldVal] + 1;
  518.                 sumSq += 2LL * freq[newVal] + 1;
  519.                 freq[newVal]++;
  520.             }
  521.             arr[pos] = newVal;
  522.         } else {
  523.             if (curL <= pos && pos <= curR) {
  524.                 freq[newVal]--;
  525.                 sumSq -= 2LL * freq[newVal] + 1;
  526.                 sumSq += 2LL * freq[oldVal] + 1;
  527.                 freq[oldVal]++;
  528.             }
  529.             arr[pos] = oldVal;
  530.         }
  531.     };
  532.  
  533.     MO_BLOCK = (int)pow(n, 2.0/3.0) + 1;
  534.     sort(queries.begin(), queries.end(), moComparator);
  535.  
  536.     for (const Query& qry : queries) {
  537.         while (curTime < qry.time) apply(updates[curTime++], true);
  538.         while (curTime > qry.time) apply(updates[--curTime], false);
  539.         while (curL > qry.L) add(--curL);
  540.         while (curR < qry.R) add(++curR);
  541.         while (curL < qry.L) remove(curL++);
  542.         while (curR > qry.R) remove(curR--);
  543.         ll len = qry.R - qry.L + 1;
  544.         ans[qry.idx] = (sumSq - len) / 2;
  545.     }
  546.     return ans;
  547. }
  548.  
  549. // -------------------------------------------------------------------
  550. // 4.6) Mode value (the most frequent element) in each query range.
  551. //      This function returns the actual value (not just its frequency)
  552. //      that appears most often. If there are ties, the smallest value
  553. //      is returned.
  554. //      Parameters: same as distinctWithUpdates.
  555. //      Returns: vector<int> answers (the value, not the frequency).
  556. //      Time complexity: O((N+Q) * N^(2/3) * log N) because we use std::set
  557. //                       internally to maintain sets of values per frequency.
  558. //      Notes: Values must be compressed for efficiency.
  559. // -------------------------------------------------------------------
  560. vector<int> modeValueWithUpdates(vector<int> arr, const vector<Update>& updates, vector<Query> queries) {
  561.     int n = (int)arr.size();
  562.     int q = (int)queries.size();
  563.     vector<int> ans(q);
  564.  
  565.     int maxVal = 0;
  566.     for (int x : arr) maxVal = max(maxVal, x);
  567.     for (auto& u : updates) maxVal = max(maxVal, max(u.oldVal, u.newVal));
  568.     vector<int> freq(maxVal + 1, 0);
  569.     vector<set<int>> valuesAtFreq(n + 1); // values that have this frequency
  570.     int curL = 0, curR = -1, curTime = 0;
  571.     int maxFreq = 0;
  572.     int modeValue = 0; // current value with maximum frequency
  573.  
  574.     auto add = [&](int idx) {
  575.         int val = arr[idx];
  576.         int f = freq[val];
  577.         if (f > 0) valuesAtFreq[f].erase(val);
  578.         freq[val]++;
  579.         valuesAtFreq[f + 1].insert(val);
  580.         if (f + 1 > maxFreq) {
  581.             maxFreq = f + 1;
  582.             modeValue = *valuesAtFreq[maxFreq].begin();
  583.         }
  584.     };
  585.  
  586.     auto remove = [&](int idx) {
  587.         int val = arr[idx];
  588.         int f = freq[val];
  589.         valuesAtFreq[f].erase(val);
  590.         freq[val]--;
  591.         if (f - 1 > 0) valuesAtFreq[f - 1].insert(val);
  592.         if (f == maxFreq && valuesAtFreq[maxFreq].empty()) {
  593.             while (maxFreq > 0 && valuesAtFreq[maxFreq].empty()) maxFreq--;
  594.             if (maxFreq > 0) modeValue = *valuesAtFreq[maxFreq].begin();
  595.             else modeValue = 0;
  596.         } else if (f == maxFreq && !valuesAtFreq[maxFreq].empty()) {
  597.             // There are other values with the same max frequency.
  598.             modeValue = *valuesAtFreq[maxFreq].begin();
  599.         }
  600.         // If f < maxFreq, modeValue remains unchanged.
  601.     };
  602.  
  603.     auto apply = [&](const Update& up, bool forward) {
  604.         int pos = up.pos;
  605.         int oldVal = up.oldVal;
  606.         int newVal = up.newVal;
  607.         if (forward) {
  608.             if (curL <= pos && pos <= curR) {
  609.                 // remove oldVal from current window
  610.                 int f = freq[oldVal];
  611.                 valuesAtFreq[f].erase(oldVal);
  612.                 freq[oldVal]--;
  613.                 if (f - 1 > 0) valuesAtFreq[f - 1].insert(oldVal);
  614.                 if (f == maxFreq && valuesAtFreq[maxFreq].empty()) {
  615.                     while (maxFreq > 0 && valuesAtFreq[maxFreq].empty()) maxFreq--;
  616.                     if (maxFreq > 0) modeValue = *valuesAtFreq[maxFreq].begin();
  617.                     else modeValue = 0;
  618.                 } else if (f == maxFreq && !valuesAtFreq[maxFreq].empty()) {
  619.                     modeValue = *valuesAtFreq[maxFreq].begin();
  620.                 }
  621.  
  622.                 // add newVal
  623.                 f = freq[newVal];
  624.                 if (f > 0) valuesAtFreq[f].erase(newVal);
  625.                 freq[newVal]++;
  626.                 valuesAtFreq[f + 1].insert(newVal);
  627.                 if (f + 1 > maxFreq) {
  628.                     maxFreq = f + 1;
  629.                     modeValue = *valuesAtFreq[maxFreq].begin();
  630.                 }
  631.             }
  632.             arr[pos] = newVal;
  633.         } else {
  634.             if (curL <= pos && pos <= curR) {
  635.                 // remove newVal
  636.                 int f = freq[newVal];
  637.                 valuesAtFreq[f].erase(newVal);
  638.                 freq[newVal]--;
  639.                 if (f - 1 > 0) valuesAtFreq[f - 1].insert(newVal);
  640.                 if (f == maxFreq && valuesAtFreq[maxFreq].empty()) {
  641.                     while (maxFreq > 0 && valuesAtFreq[maxFreq].empty()) maxFreq--;
  642.                     if (maxFreq > 0) modeValue = *valuesAtFreq[maxFreq].begin();
  643.                     else modeValue = 0;
  644.                 } else if (f == maxFreq && !valuesAtFreq[maxFreq].empty()) {
  645.                     modeValue = *valuesAtFreq[maxFreq].begin();
  646.                 }
  647.  
  648.                 // add oldVal
  649.                 f = freq[oldVal];
  650.                 if (f > 0) valuesAtFreq[f].erase(oldVal);
  651.                 freq[oldVal]++;
  652.                 valuesAtFreq[f + 1].insert(oldVal);
  653.                 if (f + 1 > maxFreq) {
  654.                     maxFreq = f + 1;
  655.                     modeValue = *valuesAtFreq[maxFreq].begin();
  656.                 }
  657.             }
  658.             arr[pos] = oldVal;
  659.         }
  660.     };
  661.  
  662.     MO_BLOCK = (int)pow(n, 2.0/3.0) + 1;
  663.     sort(queries.begin(), queries.end(), moComparator);
  664.  
  665.     for (const Query& qry : queries) {
  666.         while (curTime < qry.time) apply(updates[curTime++], true);
  667.         while (curTime > qry.time) apply(updates[--curTime], false);
  668.         while (curL > qry.L) add(--curL);
  669.         while (curR < qry.R) add(++curR);
  670.         while (curL < qry.L) remove(curL++);
  671.         while (curR > qry.R) remove(curR--);
  672.         ans[qry.idx] = modeValue;
  673.     }
  674.     return ans;
  675. }
  676.  
  677. // ===================================================================
  678. // 5) Tips and Tricks for Mo with Updates (ECPC / ACPC patterns)
  679. // ===================================================================
  680.  
  681. /*
  682.   - If the array values are large, always call compressArray() before
  683.     using any of the functions that rely on a frequency array.
  684.   - Choose block size carefully: N^(2/3) works well, but you can also
  685.     experiment with other powers.
  686.   - The comparator alternates directions to improve cache locality.
  687.   - For problems where there are no updates, you can use the simpler
  688.     Mo's algorithm (without time) which is faster. The functions above
  689.     handle the general case.
  690.   - The generic template (moSolverGeneric) is not fully provided, but
  691.     you can copy the code from any ready‑made function and change the
  692.     add/remove/apply logic to match your property.
  693.   - Common properties that are easy to maintain with MO:
  694.       * sum, product, min, max (with appropriate updates)
  695.       * distinct count
  696.       * frequency moments (sum of freq^k)
  697.       * number of pairs with equal values
  698.       * mode frequency
  699.       * median? (not recommended)
  700.   - If you need to handle multiple test cases, reinitialize all global
  701.     variables or call functions with local state (as done above).
  702. */
  703.  
  704. // ===================================================================
  705. // 6) Example Usage (main)
  706. //    This shows how to use the functions above.
  707. // ===================================================================
  708.  
  709. int main() {
  710.     ios::sync_with_stdio(false);
  711.     cin.tie(nullptr);
  712.  
  713.     // Example: array of size 5, values [1, 2, 1, 3, 2]
  714.     vector<int> arr = {1, 2, 1, 3, 2};
  715.  
  716.     // Updates: change arr[1] to 5, then arr[3] to 4
  717.     // We manually build the updates (oldVal must be known from original array).
  718.     vector<Update> updates;
  719.     updates.push_back({1, 2, 5}); // change arr[1] from 2 to 5
  720.     updates.push_back({3, 3, 4}); // change arr[3] from 3 to 4
  721.  
  722.     // Queries:
  723.     // Query 0: at time 0 (no updates applied), range [0, 2] -> should be [1,2,1]
  724.     // Query 1: at time 1 (first update applied), range [1, 3] -> after first update: [1,5,1,3,2] -> [5,1,3]
  725.     // Query 2: at time 2 (both updates applied), range [0, 4] -> [1,5,1,4,2]
  726.     vector<Query> queries;
  727.     queries.push_back({0, 2, 0, 0});
  728.     queries.push_back({1, 3, 1, 1});
  729.     queries.push_back({0, 4, 2, 2});
  730.  
  731.     // Call distinctWithUpdates
  732.     vector<int> distinctAns = distinctWithUpdates(arr, updates, queries);
  733.     cout << "Distinct answers:\n";
  734.     for (int i = 0; i < (int)distinctAns.size(); i++) {
  735.         cout << "Query " << i << ": " << distinctAns[i] << "\n";
  736.     }
  737.  
  738.     // Test sumWithUpdates
  739.     vector<ll> sumAns = sumWithUpdates(arr, updates, queries);
  740.     cout << "\nSum answers:\n";
  741.     for (int i = 0; i < (int)sumAns.size(); i++) {
  742.         cout << "Query " << i << ": " << sumAns[i] << "\n";
  743.     }
  744.  
  745.     // Test pairs equal
  746.     vector<ll> pairsAns = countPairsEqualWithUpdates(arr, updates, queries);
  747.     cout << "\nEqual pairs answers:\n";
  748.     for (int i = 0; i < (int)pairsAns.size(); i++) {
  749.         cout << "Query " << i << ": " << pairsAns[i] << "\n";
  750.     }
  751.  
  752.     return 0;
  753. }
  754.  
  755. // ===================================================================
  756. // End of Mo with Updates template
  757. // ===================================================================
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Distinct answers:
Query 0: 2
Query 1: 3
Query 2: 4

Sum answers:
Query 0: 4
Query 1: 9
Query 2: 13

Equal pairs answers:
Query 0: 1
Query 1: 0
Query 2: 1
https://ideone.com/rLLN5l
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!