fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. // ===================================================================
  6. // This file contains a collection of Sqrt Decomposition and MO's
  7. // Algorithm templates. Each function/struct is ready to be used as a
  8. // "black box". 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.  
  16. // ===================================================================
  17. // 1) Sqrt Decomposition (Static / Point Updates)
  18. //    Block decomposition splits the array into blocks of size ~sqrt(n).
  19. //    Precompute aggregate values per block.
  20. // ===================================================================
  21.  
  22. // -------------------------------------------------------------------
  23. // SqrtDecompSum: Range Sum with Point Updates
  24. // -------------------------------------------------------------------
  25. // What it does: Maintains an array and supports:
  26. //   - Point update: change value at a given index.
  27. //   - Range sum query: sum of elements in [l, r] (inclusive).
  28. // How to use:
  29. //   - Create object: SqrtDecompSum<T> ds(vector<T> a) where T is numeric.
  30. //   - update(pos, new_val): O(1) amortized? Actually O(1) per block update.
  31. //   - query(l, r): O(sqrt(n)) time.
  32. // Time complexity:
  33. //   - Build: O(n)
  34. //   - Update: O(1)
  35. //   - Query: O(sqrt(n))
  36. // Constraints:
  37. //   - Array size n can be up to ~1e5-1e6.
  38. //   - Works for any numeric type (int, long long, etc.).
  39. // Notes:
  40. //   - The array is 0-indexed.
  41. //   - Range is inclusive on both ends.
  42. // -------------------------------------------------------------------
  43. template<typename T>
  44. struct SqrtDecompSum {
  45.     int n, block_size, num_blocks;
  46.     vector<T> arr, block_sum;
  47.  
  48.     SqrtDecompSum(const vector<T>& a = {}) { init(a); }
  49.  
  50.     void init(const vector<T>& a) {
  51.         arr = a;
  52.         n = (int)arr.size();
  53.         block_size = max(1, (int)sqrt(n));
  54.         num_blocks = (n + block_size - 1) / block_size;
  55.         block_sum.assign(num_blocks, 0);
  56.         for (int i = 0; i < n; ++i) {
  57.             block_sum[i / block_size] += arr[i];
  58.         }
  59.     }
  60.  
  61.     // Point update: set arr[pos] = new_val
  62.     void update(int pos, T new_val) {
  63.         int b = pos / block_size;
  64.         block_sum[b] += (new_val - arr[pos]);
  65.         arr[pos] = new_val;
  66.     }
  67.  
  68.     // Range sum [l, r] inclusive
  69.     T query(int l, int r) {
  70.         T res = 0;
  71.         int bl = l / block_size, br = r / block_size;
  72.         if (bl == br) {
  73.             for (int i = l; i <= r; ++i) res += arr[i];
  74.         } else {
  75.             for (int i = l; i < (bl + 1) * block_size; ++i) res += arr[i];
  76.             for (int b = bl + 1; b < br; ++b) res += block_sum[b];
  77.             for (int i = br * block_size; i <= r; ++i) res += arr[i];
  78.         }
  79.         return res;
  80.     }
  81. };
  82.  
  83. // -------------------------------------------------------------------
  84. // SqrtDecompMinMax: Range Minimum/Maximum (static, no updates)
  85. // -------------------------------------------------------------------
  86. // What it does: Precomputes block-wise min and max for static array.
  87. //   - queryMin(l, r): returns minimum value in range.
  88. //   - queryMax(l, r): returns maximum value in range.
  89. // How to use:
  90. //   - Create object with array: SqrtDecompMinMax<T> ds(vector<T> a)
  91. //   - Call queryMin(l, r) or queryMax(l, r).
  92. // Time complexity:
  93. //   - Build: O(n)
  94. //   - Each query: O(sqrt(n))
  95. // Constraints:
  96. //   - Array is static; updates are not supported (if you update, you must rebuild).
  97. //   - Works for any comparable type (int, long long, etc.).
  98. // Notes:
  99. //   - 0-indexed, inclusive range.
  100. //   - For updates, you would need to rebuild the block (O(block_size)) or rebuild whole structure.
  101. // -------------------------------------------------------------------
  102. template<typename T>
  103. struct SqrtDecompMinMax {
  104.     int n, block_size, num_blocks;
  105.     vector<T> arr;
  106.     vector<T> block_min, block_max;
  107.  
  108.     SqrtDecompMinMax(const vector<T>& a = {}) { init(a); }
  109.  
  110.     void init(const vector<T>& a) {
  111.         arr = a;
  112.         n = (int)arr.size();
  113.         block_size = max(1, (int)sqrt(n));
  114.         num_blocks = (n + block_size - 1) / block_size;
  115.         block_min.assign(num_blocks, numeric_limits<T>::max());
  116.         block_max.assign(num_blocks, numeric_limits<T>::min());
  117.         for (int i = 0; i < n; ++i) {
  118.             int b = i / block_size;
  119.             block_min[b] = min(block_min[b], arr[i]);
  120.             block_max[b] = max(block_max[b], arr[i]);
  121.         }
  122.     }
  123.  
  124.     // Range minimum [l, r]
  125.     T queryMin(int l, int r) {
  126.         T res = numeric_limits<T>::max();
  127.         int bl = l / block_size, br = r / block_size;
  128.         if (bl == br) {
  129.             for (int i = l; i <= r; ++i) res = min(res, arr[i]);
  130.         } else {
  131.             for (int i = l; i < (bl + 1) * block_size; ++i) res = min(res, arr[i]);
  132.             for (int b = bl + 1; b < br; ++b) res = min(res, block_min[b]);
  133.             for (int i = br * block_size; i <= r; ++i) res = min(res, arr[i]);
  134.         }
  135.         return res;
  136.     }
  137.  
  138.     // Range maximum [l, r]
  139.     T queryMax(int l, int r) {
  140.         T res = numeric_limits<T>::min();
  141.         int bl = l / block_size, br = r / block_size;
  142.         if (bl == br) {
  143.             for (int i = l; i <= r; ++i) res = max(res, arr[i]);
  144.         } else {
  145.             for (int i = l; i < (bl + 1) * block_size; ++i) res = max(res, arr[i]);
  146.             for (int b = bl + 1; b < br; ++b) res = max(res, block_max[b]);
  147.             for (int i = br * block_size; i <= r; ++i) res = max(res, arr[i]);
  148.         }
  149.         return res;
  150.     }
  151. };
  152.  
  153. // ===================================================================
  154. // 2) MO's Algorithm (Offline Range Queries)
  155. //    Sorts queries by (L/block_size) and R, then maintains current
  156. //    range [curL, curR] by adding/removing elements.
  157. //    Complexity: O((N+Q)*sqrt(N)) for basic MO.
  158. // ===================================================================
  159.  
  160. // -------------------------------------------------------------------
  161. // MO: Generic MO structure (base class)
  162. // -------------------------------------------------------------------
  163. // What it does: Provides a framework for answering many range queries offline.
  164. //   You must derive a class and override add(), remove(), getAnswer().
  165. // How to use:
  166. //   - Create a derived class, implement the three virtual functions.
  167. //   - Call addQuery(L, R, idx) for each query.
  168. //   - Call process() to compute answers.
  169. // Time complexity: O((N+Q)*sqrt(N)) plus cost of add/remove (each O(1) ideally).
  170. // Constraints:
  171. //   - All queries must be known beforehand (offline).
  172. //   - Array indices are 0-based.
  173. // Notes:
  174. //   - The sorting uses odd-even block ordering to reduce pointer movement.
  175. //   - The array 'arr' is stored; your add/remove functions can access it.
  176. //   - Answers are stored as long long to accommodate large sums.
  177. // -------------------------------------------------------------------
  178. struct MO {
  179.     int n, block_size;
  180.     vector<int> arr;          // input array (0-indexed)
  181.     vector<long long> ans;    // answer for each query (long long for safety)
  182.     vector<tuple<int,int,int>> queries; // {L, R, idx} 0-indexed inclusive
  183.  
  184.     MO(const vector<int>& a) : arr(a) {
  185.         n = arr.size();
  186.         block_size = max(1, (int)sqrt(n));
  187.     }
  188.  
  189.     void addQuery(int L, int R, int idx) {
  190.         queries.emplace_back(L, R, idx);
  191.     }
  192.  
  193.     // Override these in a derived class
  194.     virtual void add(int pos) { /* add arr[pos] to current state */ }
  195.     virtual void remove(int pos) { /* remove arr[pos] from current state */ }
  196.     virtual long long getAnswer() { /* return current answer */ return 0; }
  197.  
  198.     void process() {
  199.         int q = queries.size();
  200.         ans.assign(q, 0);
  201.         sort(queries.begin(), queries.end(), [&](const auto& a, const auto& b) {
  202.             int blockA = get<0>(a) / block_size;
  203.             int blockB = get<0>(b) / block_size;
  204.             if (blockA != blockB) return blockA < blockB;
  205.             // For odd blocks, sort R descending to reduce movement
  206.             if (blockA & 1) return get<1>(a) > get<1>(b);
  207.             return get<1>(a) < get<1>(b);
  208.         });
  209.  
  210.         int curL = 0, curR = -1;
  211.         for (auto [L, R, idx] : queries) {
  212.             while (curL > L) add(--curL);
  213.             while (curR < R) add(++curR);
  214.             while (curL < L) remove(curL++);
  215.             while (curR > R) remove(curR--);
  216.             ans[idx] = getAnswer();
  217.         }
  218.     }
  219. };
  220.  
  221. // -------------------------------------------------------------------
  222. // MO_Distinct: Count distinct numbers in range (example)
  223. // -------------------------------------------------------------------
  224. // What it does: Answers queries for number of distinct values in [l, r].
  225. // How to use:
  226. //   - Create object: MO_Distinct mo(array)
  227. //   - Add queries with addQuery(l, r, idx)
  228. //   - Call process(), then read answers from mo.ans.
  229. // Time complexity: O((N+Q)*sqrt(N))
  230. // Constraints:
  231. //   - Array values must be <= 1,000,000 (frequency array size).
  232. //   - If values are larger, compress them first.
  233. // Notes:
  234. //   - This is a concrete implementation of the generic MO.
  235. // -------------------------------------------------------------------
  236. class MO_Distinct : public MO {
  237. public:
  238.     vector<int> freq;
  239.     int distinct;
  240.  
  241.     MO_Distinct(const vector<int>& a) : MO(a) {
  242.         freq.assign(1000005, 0); // assuming max value <= 1e6
  243.         distinct = 0;
  244.     }
  245.  
  246.     void add(int pos) override {
  247.         int x = arr[pos];
  248.         if (freq[x] == 0) ++distinct;
  249.         ++freq[x];
  250.     }
  251.  
  252.     void remove(int pos) override {
  253.         int x = arr[pos];
  254.         --freq[x];
  255.         if (freq[x] == 0) --distinct;
  256.     }
  257.  
  258.     long long getAnswer() override {
  259.         return distinct;
  260.     }
  261. };
  262.  
  263. // -------------------------------------------------------------------
  264. // MO_Sum: Sum of elements in range (example)
  265. // -------------------------------------------------------------------
  266. // What it does: Answers range sum queries.
  267. // How to use: Similar to MO_Distinct.
  268. // Time complexity: O((N+Q)*sqrt(N))
  269. // Constraints: Works for int values; sum may overflow int, but we use long long.
  270. // Notes: trivial implementation.
  271. // -------------------------------------------------------------------
  272. class MO_Sum : public MO {
  273. public:
  274.     ll current_sum;
  275.  
  276.     MO_Sum(const vector<int>& a) : MO(a) { current_sum = 0; }
  277.  
  278.     void add(int pos) override { current_sum += arr[pos]; }
  279.     void remove(int pos) override { current_sum -= arr[pos]; }
  280.     long long getAnswer() override { return current_sum; }
  281. };
  282.  
  283. // -------------------------------------------------------------------
  284. // MO_Mode: Find frequency of the mode (most frequent element) in range
  285. // -------------------------------------------------------------------
  286. // What it does: For each query, returns the maximum frequency among values in range.
  287. // How to use: Similar to above.
  288. // Time complexity: O((N+Q)*sqrt(N))
  289. // Constraints: Values must fit in frequency array (<=1e6). 
  290. // Notes: Maintains freq of each value and freqOfFreq (frequency of frequencies).
  291. // -------------------------------------------------------------------
  292. class MO_Mode : public MO {
  293. public:
  294.     vector<int> freq, freqOfFreq;
  295.     int modeFreq;
  296.  
  297.     MO_Mode(const vector<int>& a) : MO(a) {
  298.         freq.assign(1000005, 0);
  299.         freqOfFreq.assign(1000005, 0);
  300.         modeFreq = 0;
  301.     }
  302.  
  303.     void add(int pos) override {
  304.         int x = arr[pos];
  305.         if (freq[x] > 0) --freqOfFreq[freq[x]];
  306.         ++freq[x];
  307.         ++freqOfFreq[freq[x]];
  308.         modeFreq = max(modeFreq, freq[x]);
  309.     }
  310.  
  311.     void remove(int pos) override {
  312.         int x = arr[pos];
  313.         --freqOfFreq[freq[x]];
  314.         if (freq[x] == modeFreq && freqOfFreq[freq[x]] == 0) {
  315.             // The mode frequency may decrease if no other element has that frequency
  316.             while (modeFreq > 0 && freqOfFreq[modeFreq] == 0) --modeFreq;
  317.         }
  318.         --freq[x];
  319.         if (freq[x] > 0) ++freqOfFreq[freq[x]];
  320.     }
  321.  
  322.     long long getAnswer() override {
  323.         return modeFreq;
  324.     }
  325. };
  326.  
  327. // ===================================================================
  328. // 3) MO with Updates (MO's Algorithm with Modifications)
  329. //    Handles point updates interleaved with queries.
  330. //    Complexity: O( (N+Q)^(5/3) ) ~ O( (N+Q)*N^(2/3) ) with block size N^(2/3).
  331. // ===================================================================
  332.  
  333. // -------------------------------------------------------------------
  334. // MOWithUpdates: MO algorithm that supports point updates.
  335. // -------------------------------------------------------------------
  336. // What it does: Processes queries with updates in between.
  337. //   It supports two operations:
  338. //     1. Point update: change value at position pos to new_val.
  339. //     2. Range query: e.g., count distinct numbers in [l, r].
  340. // How to use:
  341. //   - Create object with initial array.
  342. //   - Add queries with addQuery(l, r, idx) and updates with addUpdate(pos, new_val).
  343. //   - Call process() to compute answers.
  344. // Time complexity: O( (N+Q)^(5/3) ) ~ O( (N+Q)*N^(2/3) )
  345. // Constraints:
  346. //   - Array values must fit in frequency array (size 1e6+5).
  347. //   - All queries and updates must be known beforehand.
  348. // Notes:
  349. //   - The block size is chosen as N^(2/3) for optimal performance.
  350. //   - The implementation here counts distinct numbers; you can adapt the lambda functions.
  351. //   - The internal array 'arr' is modified during processing, but original is preserved.
  352. // -------------------------------------------------------------------
  353. struct MOWithUpdates {
  354.     struct Query {
  355.         int l, r, t, idx;
  356.     };
  357.     struct Update {
  358.         int pos, old_val, new_val;
  359.     };
  360.  
  361.     int n, q, u; // u = number of updates
  362.     vector<int> arr;          // This will hold the array state while reading updates (for old_val)
  363.     vector<int> initial_arr;  // Original array (copied from constructor) for processing
  364.     vector<Query> queries;
  365.     vector<Update> updates;
  366.     vector<int> ans;
  367.  
  368.     MOWithUpdates(const vector<int>& a) : arr(a), initial_arr(a) {
  369.         n = arr.size();
  370.         q = u = 0;
  371.     }
  372.  
  373.     void addQuery(int l, int r, int idx) {
  374.         queries.push_back({l, r, (int)updates.size(), idx});
  375.     }
  376.  
  377.     // Add a point update: set arr[pos] = new_val.
  378.     // IMPORTANT: This modifies the internal array 'arr' to compute the correct old_val for later updates.
  379.     // The original array is preserved in 'initial_arr' for processing.
  380.     void addUpdate(int pos, int new_val) {
  381.         int old_val = arr[pos];
  382.         updates.push_back({pos, old_val, new_val});
  383.         arr[pos] = new_val; // Update the current state for subsequent updates
  384.     }
  385.  
  386.     void process() {
  387.         q = queries.size();
  388.         ans.assign(q, 0);
  389.         int block_size = pow(n, 2.0/3.0); // typical block size for MO with updates
  390.         sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
  391.             int blockL_a = a.l / block_size;
  392.             int blockL_b = b.l / block_size;
  393.             if (blockL_a != blockL_b) return blockL_a < blockL_b;
  394.             int blockR_a = a.r / block_size;
  395.             int blockR_b = b.r / block_size;
  396.             if (blockR_a != blockR_b) return blockR_a < blockR_b;
  397.             return a.t < b.t;
  398.         });
  399.  
  400.         vector<int> curArr = initial_arr; // start with the original array
  401.         int curL = 0, curR = -1, curT = 0;
  402.  
  403.         // For this example we count distinct numbers. 
  404.         // Frequency array size fixed to 1e6+5; ensure values are within that range.
  405.         vector<int> freq(1000005, 0);
  406.         int distinct = 0;
  407.  
  408.         auto addPos = [&](int pos) {
  409.             int x = curArr[pos];
  410.             if (freq[x] == 0) ++distinct;
  411.             ++freq[x];
  412.         };
  413.         auto removePos = [&](int pos) {
  414.             int x = curArr[pos];
  415.             --freq[x];
  416.             if (freq[x] == 0) --distinct;
  417.         };
  418.         auto applyUpdate = [&](int t, bool forward) {
  419.             // forward = true: apply update t (change from old_val to new_val)
  420.             // forward = false: rollback update t (change from new_val back to old_val)
  421.             Update& upd = updates[t];
  422.             int pos = upd.pos;
  423.             int oldVal = upd.old_val;
  424.             int newVal = upd.new_val;
  425.             bool inRange = (curL <= pos && pos <= curR);
  426.             if (inRange) {
  427.                 // Remove the current value (oldVal if forward, newVal if rollback)
  428.                 int currentVal = curArr[pos];
  429.                 --freq[currentVal];
  430.                 if (freq[currentVal] == 0) --distinct;
  431.             }
  432.             // Apply the change to the array
  433.             if (forward) {
  434.                 curArr[pos] = newVal;
  435.             } else {
  436.                 curArr[pos] = oldVal;
  437.             }
  438.             if (inRange) {
  439.                 // Add the new value
  440.                 int newCurrent = curArr[pos];
  441.                 if (freq[newCurrent] == 0) ++distinct;
  442.                 ++freq[newCurrent];
  443.             }
  444.         };
  445.  
  446.         for (auto& qu : queries) {
  447.             // Adjust L and R
  448.             while (curL > qu.l) addPos(--curL);
  449.             while (curR < qu.r) addPos(++curR);
  450.             while (curL < qu.l) removePos(curL++);
  451.             while (curR > qu.r) removePos(curR--);
  452.             // Adjust time
  453.             while (curT < qu.t) {
  454.                 applyUpdate(curT, true);
  455.                 ++curT;
  456.             }
  457.             while (curT > qu.t) {
  458.                 --curT;
  459.                 applyUpdate(curT, false);
  460.             }
  461.             ans[qu.idx] = distinct;
  462.         }
  463.     }
  464. };
  465.  
  466. // ===================================================================
  467. // 4) MO on Trees (Path Queries)
  468. //    For tree path queries, we flatten the tree using Euler tour.
  469. //    For each node, we store first occurrence and last occurrence in Euler tour.
  470. //    Then path queries become range queries on the Euler array.
  471. //    Need to handle LCA to avoid double counting.
  472. // ===================================================================
  473.  
  474. // -------------------------------------------------------------------
  475. // MOOnTree: MO algorithm for path queries on a tree.
  476. // -------------------------------------------------------------------
  477. // What it does: Answers queries about a path between two nodes in a tree.
  478. //   For example, count distinct values on the path.
  479. // How to use:
  480. //   - Create object with number of nodes N.
  481. //   - Add edges with addEdge(u, v).
  482. //   - Set values for each node in 'value' array.
  483. //   - Call preprocessLCA(root) to build Euler tour and LCA table.
  484. //   - Add queries with addQuery(u, v, idx).
  485. //   - Call process() to compute answers.
  486. // Time complexity:
  487. //   - Preprocessing: O(N log N) for LCA.
  488. //   - Query processing: O((N+Q)*sqrt(N)) where N is number of nodes (Euler length 2N).
  489. // Constraints:
  490. //   - Tree is 0-indexed.
  491. //   - Values must fit in frequency array (1e6+5).
  492. //   - The tree is static; no updates.
  493. // Notes:
  494. //   - The Euler tour length is 2N.
  495. //   - For each query, we compute the range [l, r] and possibly add LCA separately.
  496. //   - The current implementation counts distinct values on path (you can modify toggle function).
  497. //   - The LCA is computed using binary lifting.
  498. // -------------------------------------------------------------------
  499. struct MOOnTree {
  500.     int n, q;
  501.     vector<vector<int>> adj;
  502.     vector<int> value;   // value of each node
  503.     vector<int> euler;   // Euler tour of length 2n
  504.     vector<int> first, last; // first and last occurrence in Euler
  505.     vector<int> depth, parent, lg;
  506.     vector<vector<int>> up; // binary lifting for LCA
  507.  
  508.     MOOnTree(int n) : n(n) {
  509.         adj.assign(n, {});
  510.         value.assign(n, 0);
  511.         first.assign(n, -1);
  512.         last.assign(n, -1);
  513.         depth.assign(n, 0);
  514.         parent.assign(n, 0);
  515.     }
  516.  
  517.     void addEdge(int u, int v) {
  518.         adj[u].push_back(v);
  519.         adj[v].push_back(u);
  520.     }
  521.  
  522.     void dfs(int u, int p) {
  523.         parent[u] = p;
  524.         first[u] = euler.size();
  525.         euler.push_back(u);
  526.         for (int v : adj[u]) {
  527.             if (v == p) continue;
  528.             depth[v] = depth[u] + 1;
  529.             dfs(v, u);
  530.         }
  531.         last[u] = euler.size();
  532.         euler.push_back(u);
  533.     }
  534.  
  535.     // LCA preprocessing
  536.     void preprocessLCA(int root = 0) {
  537.         dfs(root, root);
  538.         int LOG = 1;
  539.         while ((1 << LOG) <= n) ++LOG;
  540.         up.assign(LOG, vector<int>(n));
  541.         up[0] = parent;
  542.         for (int j = 1; j < LOG; ++j) {
  543.             for (int i = 0; i < n; ++i) {
  544.                 up[j][i] = up[j-1][ up[j-1][i] ];
  545.             }
  546.         }
  547.     }
  548.  
  549.     int lca(int u, int v) {
  550.         if (depth[u] < depth[v]) swap(u, v);
  551.         int diff = depth[u] - depth[v];
  552.         for (int j = 0; diff; ++j, diff >>= 1) {
  553.             if (diff & 1) u = up[j][u];
  554.         }
  555.         if (u == v) return u;
  556.         for (int j = up.size() - 1; j >= 0; --j) {
  557.             if (up[j][u] != up[j][v]) {
  558.                 u = up[j][u];
  559.                 v = up[j][v];
  560.             }
  561.         }
  562.         return parent[u];
  563.     }
  564.  
  565.     struct Query {
  566.         int l, r, idx, lcaNode;
  567.         bool addLca;
  568.     };
  569.  
  570.     vector<Query> queries;
  571.     vector<int> ans;
  572.  
  573.     void addQuery(int u, int v, int idx) {
  574.         if (first[u] > first[v]) swap(u, v);
  575.         int w = lca(u, v);
  576.         Query q;
  577.         q.idx = idx;
  578.         q.addLca = false;
  579.         q.lcaNode = w;
  580.         if (w == u) {
  581.             q.l = first[u];
  582.             q.r = first[v];
  583.         } else {
  584.             q.l = last[u];
  585.             q.r = first[v];
  586.             q.addLca = true;
  587.         }
  588.         queries.push_back(q);
  589.     }
  590.  
  591.     void process() {
  592.         q = queries.size();
  593.         ans.assign(q, 0);
  594.         int block_size = max(1, (int)sqrt(2 * n));
  595.         sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
  596.             int blockA = a.l / block_size;
  597.             int blockB = b.l / block_size;
  598.             if (blockA != blockB) return blockA < blockB;
  599.             if (blockA & 1) return a.r > b.r;
  600.             return a.r < b.r;
  601.         });
  602.  
  603.         vector<bool> vis(n, false);
  604.         vector<int> freq(1000005, 0); // assuming values range
  605.         int distinct = 0;
  606.  
  607.         auto toggle = [&](int node) {
  608.             if (vis[node]) {
  609.                 // remove
  610.                 int x = value[node];
  611.                 --freq[x];
  612.                 if (freq[x] == 0) --distinct;
  613.                 vis[node] = false;
  614.             } else {
  615.                 // add
  616.                 int x = value[node];
  617.                 if (freq[x] == 0) ++distinct;
  618.                 ++freq[x];
  619.                 vis[node] = true;
  620.             }
  621.         };
  622.  
  623.         int curL = 0, curR = -1;
  624.         for (auto& q : queries) {
  625.             while (curL > q.l) toggle(euler[--curL]);
  626.             while (curR < q.r) toggle(euler[++curR]);
  627.             while (curL < q.l) toggle(euler[curL++]);
  628.             while (curR > q.r) toggle(euler[curR--]);
  629.             int curAns = distinct;
  630.             if (q.addLca) {
  631.                 // add LCA temporarily
  632.                 int x = value[q.lcaNode];
  633.                 if (freq[x] == 0) ++curAns;
  634.                 // Note: we do not modify freq permanently; just compute answer
  635.             }
  636.             ans[q.idx] = curAns;
  637.         }
  638.     }
  639. };
  640.  
  641. // ===================================================================
  642. // 5) Advanced Tricks & Patterns
  643. // ===================================================================
  644.  
  645. // -------------------------------------------------------------------
  646. // Hilbert Order for MO (improved cache performance)
  647. // -------------------------------------------------------------------
  648. // What it does: Computes a Hilbert curve order for a point (x, y).
  649. //   Using this order for sorting MO queries can reduce pointer movement.
  650. // How to use:
  651. //   - In your MO processing, sort queries using hilbertOrder(l, r, pow, 0)
  652. //     where pow is such that 2^pow > max(N, Q). Typically pow=21 for 2e6.
  653. //   - Example: sort by hilbertOrder(a.l, a.r, 21, 0) < hilbertOrder(b.l, b.r, 21, 0)
  654. // Time complexity: O(1) per call (recursive depth ~pow).
  655. // Constraints: x and y should be non-negative and less than 2^pow.
  656. // Notes: This is an alternative to odd-even block sorting; often faster.
  657. // -------------------------------------------------------------------
  658. long long hilbertOrder(int x, int y, int pow, int rotate) {
  659.     if (pow == 0) return 0;
  660.     int hpow = 1 << (pow - 1);
  661.     int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
  662.     seg = (seg + rotate) & 3;
  663.     static const int rotateDelta[4] = {3, 0, 0, 1};
  664.     int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
  665.     int nrot = (rotate + rotateDelta[seg]) & 3;
  666.     long long subSquareSize = 1LL << (2 * pow - 2);
  667.     long long ord = seg * subSquareSize;
  668.     long long add = hilbertOrder(nx, ny, pow - 1, nrot);
  669.     ord += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
  670.     return ord;
  671. }
  672.  
  673. // -------------------------------------------------------------------
  674. // SqrtQueryDecomp: Process queries in blocks of sqrt(Q)
  675. // -------------------------------------------------------------------
  676. // What it does: Handles a mix of updates and queries by processing them in blocks.
  677. //   At the start of each block, we have a snapshot of the array.
  678. //   Within the block, we apply updates sequentially and answer queries on the fly.
  679. // How to use:
  680. //   - Create object with initial array.
  681. //   - Add updates with addUpdate(pos, new_val) and queries with addQuery(l, r, idx).
  682. //   - Call process() to get answers.
  683. // Time complexity: O( (updates + queries) * sqrt(queries) * cost of query answer )
  684. //   Here query answer is O(range length) in this naive implementation (which is slow).
  685. //   For a proper implementation, you'd optimize query answering.
  686. // Constraints:
  687. //   - All operations are known offline.
  688. //   - The current implementation answers sum queries in O(r-l+1) which defeats the purpose.
  689. //     It is just a demonstration of the block decomposition concept.
  690. // Notes: This is a different approach from MO; it's useful when updates are frequent.
  691. // -------------------------------------------------------------------
  692. struct SqrtQueryDecomp {
  693.     int n, q;
  694.     vector<int> arr;
  695.     vector<tuple<int,int,int,int>> queries; // type, l, r, idx (type=0 update, type=1 query)
  696.     int block_size;
  697.  
  698.     SqrtQueryDecomp(const vector<int>& a) : arr(a) {
  699.         n = arr.size();
  700.         q = 0;
  701.         block_size = max(1, (int)sqrt(1)); // will set later
  702.     }
  703.  
  704.     void addUpdate(int pos, int new_val) {
  705.         queries.emplace_back(0, pos, new_val, -1);
  706.     }
  707.     void addQuery(int l, int r, int idx) {
  708.         queries.emplace_back(1, l, r, idx);
  709.     }
  710.  
  711.     vector<int> ans;
  712.  
  713.     void process() {
  714.         q = queries.size();
  715.         ans.assign(q, 0);
  716.         block_size = max(1, (int)sqrt(q));
  717.         // Process each block of queries
  718.         for (int b = 0; b < q; b += block_size) {
  719.             int end = min(q, b + block_size);
  720.             vector<int> cur = arr;
  721.             for (int i = b; i < end; ++i) {
  722.                 auto& qu = queries[i];
  723.                 int type = get<0>(qu);
  724.                 if (type == 0) { // update
  725.                     int pos = get<1>(qu);
  726.                     int new_val = get<2>(qu);
  727.                     cur[pos] = new_val;
  728.                 } else { // query
  729.                     int l = get<1>(qu);
  730.                     int r = get<2>(qu);
  731.                     int idx = get<3>(qu);
  732.                     long long sum = 0;
  733.                     for (int j = l; j <= r; ++j) sum += cur[j];
  734.                     ans[idx] = sum;
  735.                 }
  736.             }
  737.             arr = cur; // apply all updates in this block for next block
  738.         }
  739.     }
  740. };
  741.  
  742. // -------------------------------------------------------------------
  743. // SqrtBitset: Use bitsets with sqrt decomposition
  744. // -------------------------------------------------------------------
  745. // What it does: Stores a bitset of values present in each block.
  746. //   Allows fast set operations (union, intersection) on ranges.
  747. // How to use:
  748. //   - Create object with array: SqrtBitset sb(arr)
  749. //   - Call queryBitset(l, r) to get a bitset of distinct values in range.
  750. //   - Use countDistinct(l, r) for count, contains(l, r, x) to test presence.
  751. // Time complexity:
  752. //   - Build: O(n)
  753. //   - queryBitset: O(sqrt(n) * (bitset_size / word_size))? Actually O(blocks + partial) but bitset OR is fast.
  754. //   - For each range, we OR block bitsets and set individual elements.
  755. // Constraints:
  756. //   - Maximum value must be less than MAXV (here 100000). Adjust constant as needed.
  757. //   - Array is static.
  758. // Notes: Bitset is a data structure that represents a set of bits (booleans) efficiently.
  759. //   A bitset of size MAXV uses MAXV/8 bytes of memory.
  760. //   The OR operation combines bitsets quickly.
  761. // -------------------------------------------------------------------
  762. #include <bitset>
  763. const int MAXV = 100000; // maximum value
  764.  
  765. struct SqrtBitset {
  766.     int n, block_size, num_blocks;
  767.     vector<int> arr;
  768.     vector< bitset<MAXV> > block_bits; // bitset per block
  769.  
  770.     SqrtBitset(const vector<int>& a) {
  771.         arr = a;
  772.         n = arr.size();
  773.         block_size = max(1, (int)sqrt(n));
  774.         num_blocks = (n + block_size - 1) / block_size;
  775.         block_bits.resize(num_blocks);
  776.         for (int i = 0; i < n; ++i) {
  777.             block_bits[i / block_size].set(arr[i]);
  778.         }
  779.     }
  780.  
  781.     // Query: return bitset of distinct values in range [l,r]
  782.     bitset<MAXV> queryBitset(int l, int r) {
  783.         bitset<MAXV> res;
  784.         int bl = l / block_size, br = r / block_size;
  785.         if (bl == br) {
  786.             for (int i = l; i <= r; ++i) res.set(arr[i]);
  787.         } else {
  788.             for (int i = l; i < (bl+1)*block_size; ++i) res.set(arr[i]);
  789.             for (int b = bl+1; b < br; ++b) res |= block_bits[b];
  790.             for (int i = br*block_size; i <= r; ++i) res.set(arr[i]);
  791.         }
  792.         return res;
  793.     }
  794.  
  795.     // Count distinct values in range
  796.     int countDistinct(int l, int r) {
  797.         return queryBitset(l, r).count();
  798.     }
  799.  
  800.     // Check if range contains value x
  801.     bool contains(int l, int r, int x) {
  802.         return queryBitset(l, r).test(x);
  803.     }
  804.  
  805.     // Union of two ranges: bitset OR
  806.     bitset<MAXV> unionRanges(int l1, int r1, int l2, int r2) {
  807.         return queryBitset(l1, r1) | queryBitset(l2, r2);
  808.     }
  809. };
  810.  
  811. // -------------------------------------------------------------------
  812. // Coordinate compression for array values
  813. // -------------------------------------------------------------------
  814. // What it does: Maps large values to a smaller range [0, m-1].
  815. //   Useful for MO when values are large and need to fit in frequency arrays.
  816. // How to use:
  817. //   - Pass your array to compressArray().
  818. //   - It returns a new array with compressed values.
  819. // Time complexity: O(n log n) due to sorting.
  820. // Constraints: None.
  821. // Notes: The original values are sorted and each gets a unique id.
  822. //   The compressed values preserve order.
  823. // -------------------------------------------------------------------
  824. vector<int> compressArray(const vector<int>& a) {
  825.     vector<int> vals = a;
  826.     sort(vals.begin(), vals.end());
  827.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  828.     vector<int> res(a.size());
  829.     for (int i = 0; i < (int)a.size(); ++i) {
  830.         res[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
  831.     }
  832.     return res;
  833. }
  834.  
  835. // ===================================================================
  836. // 6) Example usage (commented)
  837. // ===================================================================
  838.  
  839. int main() {
  840.     ios::sync_with_stdio(false);
  841.     cin.tie(nullptr);
  842.  
  843.     // Sqrt Decomposition Sum
  844.     vector<int> arr = {1, 2, 3, 4, 5};
  845.     SqrtDecompSum<int> sd(arr);
  846.     cout << sd.query(1, 3) << '\n'; // 2+3+4=9
  847.     sd.update(2, 10);
  848.     cout << sd.query(1, 3) << '\n'; // 2+10+4=16
  849.  
  850.     // MO Distinct
  851.     vector<int> a = {1, 2, 3, 2, 1, 4};
  852.     MO_Distinct mo(a);
  853.     mo.addQuery(0, 2, 0);
  854.     mo.addQuery(1, 4, 1);
  855.     mo.addQuery(2, 5, 2);
  856.     mo.process();
  857.     for (long long x : mo.ans) cout << x << ' '; // 3, 2, 3
  858.     cout << '\n';
  859.  
  860.     // MO with Updates (example)
  861.     vector<int> b = {1, 2, 3, 4};
  862.     MOWithUpdates mow(b);
  863.     mow.addQuery(0, 2, 0);
  864.     mow.addUpdate(1, 5); // index 1 becomes 5
  865.     mow.addQuery(0, 2, 1);
  866.     mow.process();
  867.     // answers: distinct in [0,2] initially: 1,2,3 => 3; after update: 1,5,3 => 3
  868.     for (int x : mow.ans) cout << x << ' ';
  869.     cout << '\n';
  870.  
  871.     // MO on Tree (example tree with 5 nodes)
  872.     MOOnTree mot(5);
  873.     mot.addEdge(0, 1);
  874.     mot.addEdge(0, 2);
  875.     mot.addEdge(1, 3);
  876.     mot.addEdge(1, 4);
  877.     mot.value = {1, 2, 3, 4, 5};
  878.     mot.preprocessLCA(0);
  879.     mot.addQuery(2, 3, 0); // path 2-0-1-3: values 3,1,2,4 => distinct 4
  880.     mot.addQuery(3, 4, 1); // path 3-1-4: values 4,2,5 => distinct 3
  881.     mot.process();
  882.     for (int x : mot.ans) cout << x << ' ';
  883.     cout << '\n';
  884.  
  885.     return 0;
  886. }
  887.  
  888. // ===================================================================
  889. // End of template
  890. // ===================================================================
Success #stdin #stdout 0.01s 11472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9
16
3 3 4 
3 3 
4 3
https://ideone.com/CKgRFh
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!