fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5. ============================================================
  6.                     SMALL-TO-LARGE TEMPLATE
  7.           Collected ideas and tricks for ECPC & ACPC
  8. ============================================================
  9.  
  10. Contents:
  11. 1) Merging different containers (set, map, vector, priority_queue)
  12. 2) DSU on Tree (Sack) with custom add/remove functions
  13. 3) Merging Maps to calculate answers for each node
  14. 4) Advanced techniques: Subtree queries
  15. 5) Examples of common problems (color count, sum, GCD, Mex, ...)
  16. 6) Handling offline queries
  17. 7) Performance improvements (swap, clear, move)
  18.  
  19. Everyone uses the idea "merge the small into the large" to get O(n log n) or O(n log^2 n).
  20. ============================================================
  21. */
  22.  
  23. // ==========================================================
  24. // 1) Basic container merge functions
  25. // ==========================================================
  26.  
  27. // -------- Merge unordered_map (same key) --------
  28. /**
  29.  * PURPOSE:
  30.  *   Merges two unordered_maps by summing values for same keys.
  31.  *   After merging, the larger map (a) will contain the combined data,
  32.  *   and the smaller map (b) will be cleared.
  33.  *
  34.  * HOW TO USE:
  35.  *   Call mergeUnorderedMap(a, b) where:
  36.  *   - a: the primary map (will hold the final merged result)
  37.  *   - b: the map to merge into a (will be emptied)
  38.  *
  39.  * TIME COMPLEXITY:
  40.  *   O(size_of_smaller_map) on average.
  41.  *
  42.  * NOTES:
  43.  *   - The function ensures that the larger map is the one kept.
  44.  *   - Values are added using +=. If you need different logic (e.g., assignment),
  45.  *     modify the line a[k] += v.
  46.  *
  47.  * CONSTRAINTS:
  48.  *   - The keys must support operator[] and iteration.
  49.  *   - Works with any types that support +=.
  50.  */
  51. template<typename K, typename V>
  52. void mergeUnorderedMap(unordered_map<K,V>& a, unordered_map<K,V>& b) {
  53.     if (a.size() < b.size()) a.swap(b);
  54.     for (auto &[k, v] : b)
  55.         a[k] += v;
  56.     b.clear();
  57. }
  58.  
  59. // -------- Merge map (ordered) --------
  60. /**
  61.  * PURPOSE:
  62.  *   Merges two ordered maps by summing values for same keys.
  63.  *   After merging, the larger map (a) will contain the combined data,
  64.  *   and the smaller map (b) will be cleared.
  65.  *
  66.  * HOW TO USE:
  67.  *   Call mergeMap(a, b) where:
  68.  *   - a: the primary map (will hold the final merged result)
  69.  *   - b: the map to merge into a (will be emptied)
  70.  *
  71.  * TIME COMPLEXITY:
  72.  *   O(size_of_smaller_map * log(size_of_larger_map)) because each insertion into
  73.  *   the larger map costs O(log n).
  74.  *
  75.  * NOTES:
  76.  *   - The function ensures that the larger map is the one kept.
  77.  *   - Values are added using +=. If you need different logic, modify the line.
  78.  *
  79.  * CONSTRAINTS:
  80.  *   - Keys must be comparable (operator<) because std::map is ordered.
  81.  */
  82. template<typename K, typename V>
  83. void mergeMap(map<K,V>& a, map<K,V>& b) {
  84.     if (a.size() < b.size()) a.swap(b);
  85.     for (auto &[k, v] : b)
  86.         a[k] += v;
  87.     b.clear();
  88. }
  89.  
  90. // -------- Merge set --------
  91. /**
  92.  * PURPOSE:
  93.  *   Merges two sets into one. The resulting set contains all unique elements
  94.  *   from both sets. The larger set (a) will hold the final result, and the
  95.  *   smaller set (b) will be cleared.
  96.  *
  97.  * HOW TO USE:
  98.  *   Call mergeSet(a, b) where:
  99.  *   - a: the primary set (will hold the final merged result)
  100.  *   - b: the set to merge into a (will be emptied)
  101.  *
  102.  * TIME COMPLEXITY:
  103.  *   O(size_of_smaller_set * log(size_of_larger_set)).
  104.  *
  105.  * NOTES:
  106.  *   - The function ensures that the larger set is the one kept.
  107.  *   - Duplicates are automatically handled because std::set only stores unique
  108.  *     elements.
  109.  *
  110.  * CONSTRAINTS:
  111.  *   - Elements must be comparable (operator<) because std::set is ordered.
  112.  */
  113. template<typename T>
  114. void mergeSet(set<T>& a, set<T>& b) {
  115.     if (a.size() < b.size()) a.swap(b);
  116.     for (auto &x : b) a.insert(x);
  117.     b.clear();
  118. }
  119.  
  120. // -------- Merge vector --------
  121. /**
  122.  * PURPOSE:
  123.  *   Merges two vectors by appending all elements of b to a.
  124.  *   After merging, the larger vector (a) will contain all elements from both,
  125.  *   and the smaller vector (b) will be cleared.
  126.  *
  127.  * HOW TO USE:
  128.  *   Call mergeVector(a, b) where:
  129.  *   - a: the primary vector (will hold the final merged result)
  130.  *   - b: the vector to merge into a (will be emptied)
  131.  *
  132.  * TIME COMPLEXITY:
  133.  *   O(size_of_smaller_vector) for the insertion.
  134.  *
  135.  * NOTES:
  136.  *   - The function ensures that the larger vector is the one kept.
  137.  *   - Order is preserved: elements from a come first, then elements from b.
  138.  *   - No deduplication is performed; duplicates remain.
  139.  *
  140.  * CONSTRAINTS:
  141.  *   - Works with any type.
  142.  */
  143. template<typename T>
  144. void mergeVector(vector<T>& a, vector<T>& b) {
  145.     if (a.size() < b.size()) a.swap(b);
  146.     a.insert(a.end(), b.begin(), b.end());
  147.     b.clear();
  148. }
  149.  
  150. // -------- Merge priority_queue --------
  151. /**
  152.  * PURPOSE:
  153.  *   Merges two priority_queues by transferring all elements from b to a.
  154.  *   After merging, a will contain all elements from both queues,
  155.  *   and b will be empty.
  156.  *
  157.  * HOW TO USE:
  158.  *   Call mergePriorityQueue(a, b) where:
  159.  *   - a: the primary priority_queue (will hold the final merged result)
  160.  *   - b: the priority_queue to merge into a (will be emptied)
  161.  *
  162.  * TIME COMPLEXITY:
  163.  *   O(size_of_smaller_queue * log(size_of_larger_queue)).
  164.  *
  165.  * NOTES:
  166.  *   - The function does NOT automatically swap to keep the larger one because
  167.  *     priority_queue does not support size-based swapping efficiently.
  168.  *   - This method is less efficient than using a vector as the underlying
  169.  *     container. Consider using a vector and building a heap instead.
  170.  *
  171.  * CONSTRAINTS:
  172.  *   - Works with any type that priority_queue supports.
  173.  */
  174. template<typename T>
  175. void mergePriorityQueue(priority_queue<T>& a, priority_queue<T>& b) {
  176.     while (!b.empty()) {
  177.         a.push(b.top());
  178.         b.pop();
  179.     }
  180. }
  181.  
  182. // ==========================================================
  183. // 2) DSU on Tree (Sack) – General model with add/remove functions
  184. // ==========================================================
  185.  
  186. /**
  187.  * PURPOSE:
  188.  *   This structure solves subtree queries on a tree using the DSU on Tree
  189.  *   (also called "Sack") technique. It computes an answer for each node based
  190.  *   on the properties of its entire subtree.
  191.  *
  192.  *   Examples of what can be computed:
  193.  *   - Number of distinct colors in each subtree
  194.  *   - Sum of values in each subtree
  195.  *   - GCD, Mex, mode, etc.
  196.  *
  197.  * HOW TO USE:
  198.  *   1. Create an instance: DSUonTree solver(n); where n is the number of nodes.
  199.  *   2. Add edges using solver.addEdge(u, v) (0-indexed nodes).
  200.  *   3. Customize the addNode() function to update your data when a node is
  201.  *      added or removed.
  202.  *   4. Call solver.solve().
  203.  *   5. Results are stored in solver.ans[u] for each node u.
  204.  *
  205.  * TIME COMPLEXITY:
  206.  *   O(n log n) for the DFS, plus the cost of addNode/removeNode for each node
  207.  *   (which is O(1) in most cases). If addNode uses a BIT or map, complexity
  208.  *   increases accordingly.
  209.  *
  210.  * NOTES:
  211.  *   - "Heavy child" means the child with the largest subtree size.
  212.  *   - "Keep" flag: if true, the subtree's data is kept after the DFS; if false,
  213.  *     it is removed to free memory.
  214.  *   - The provided addNode example tracks distinct colors. You must adapt it
  215.  *     to your specific problem.
  216.  *
  217.  * CONSTRAINTS:
  218.  *   - n must be at least 1.
  219.  *   - Node IDs must be from 0 to n-1.
  220.  *   - The graph must be a tree (connected, acyclic).
  221.  */
  222. struct DSUonTree {
  223.     int n;
  224.     vector<vector<int>> adj;
  225.     vector<int> sz, heavy;
  226.     vector<int> ans;
  227.  
  228.     // Example data: frequency of colors
  229.     vector<int> freq;
  230.     int distinct = 0;
  231.  
  232.     DSUonTree(int n) : n(n), adj(n), sz(n, 1), heavy(n, -1), ans(n), freq(n+1, 0) {}
  233.  
  234.     void addEdge(int u, int v) {
  235.         adj[u].push_back(v);
  236.         adj[v].push_back(u);
  237.     }
  238.  
  239.     // Computes subtree sizes and identifies the heavy child for each node.
  240.     void dfsSize(int u, int p) {
  241.         sz[u] = 1;
  242.         int mx = 0;
  243.         for (int v : adj[u]) {
  244.             if (v == p) continue;
  245.             dfsSize(v, u);
  246.             sz[u] += sz[v];
  247.             if (sz[v] > mx) {
  248.                 mx = sz[v];
  249.                 heavy[u] = v;
  250.             }
  251.         }
  252.     }
  253.  
  254.     // Add or remove a single node and all its descendants from the data.
  255.     // delta = +1 to add, -1 to remove.
  256.     void addNode(int u, int p, int delta) {
  257.         int color = u; // Example: color = node ID. Change as needed.
  258.         if (delta == 1) {
  259.             if (freq[color] == 0) distinct++;
  260.             freq[color]++;
  261.         } else {
  262.             freq[color]--;
  263.             if (freq[color] == 0) distinct--;
  264.         }
  265.         for (int v : adj[u]) {
  266.             if (v == p) continue;
  267.             addNode(v, u, delta);
  268.         }
  269.     }
  270.  
  271.     void addSubtree(int u, int p, int delta) {
  272.         addNode(u, p, delta);
  273.     }
  274.  
  275.     // Main DSU on Tree DFS.
  276.     // keep = true means we keep the data after finishing this subtree.
  277.     void dfs(int u, int p, bool keep) {
  278.         // Solve light children and clear their data.
  279.         for (int v : adj[u]) {
  280.             if (v == p || v == heavy[u]) continue;
  281.             dfs(v, u, false);
  282.         }
  283.         // Solve heavy child and keep its data.
  284.         if (heavy[u] != -1) {
  285.             dfs(heavy[u], u, true);
  286.         }
  287.         // Add light subtrees and the current node.
  288.         for (int v : adj[u]) {
  289.             if (v == p || v == heavy[u]) continue;
  290.             addSubtree(v, u, +1);
  291.         }
  292.         addNode(u, p, +1);
  293.  
  294.         // Now the data represents the entire subtree of u. Compute answer.
  295.         ans[u] = distinct; // Example: distinct colors.
  296.  
  297.         // If keep is false, remove this entire subtree's data.
  298.         if (!keep) {
  299.             addSubtree(u, p, -1);
  300.         }
  301.     }
  302.  
  303.     void solve() {
  304.         dfsSize(0, -1);
  305.         dfs(0, -1, false);
  306.     }
  307. };
  308.  
  309. // ==========================================================
  310. // 3) Merging Maps to calculate answers for each node (without Sack)
  311. // ==========================================================
  312.  
  313. /**
  314.  * PURPOSE:
  315.  *   Merges two maps and updates a global answer variable during the merge.
  316.  *   This is useful when you need to compute something like the number of equal
  317.  *   pairs across combined data.
  318.  *
  319.  * HOW TO USE:
  320.  *   Call mergeMapAndCompute(a, b, answer) where:
  321.  *   - a: the larger map (will hold the merged result)
  322.  *   - b: the smaller map (will be merged into a and cleared)
  323.  *   - answer: a reference to a variable that stores the computed result
  324.  *
  325.  * TIME COMPLEXITY:
  326.  *   O(size_of_smaller_map * log(size_of_larger_map)).
  327.  *
  328.  * NOTES:
  329.  *   - The function ensures that the larger map is kept.
  330.  *   - The example computes the number of equal-value pairs.
  331.  *   - You must adapt the logic inside the loop to your specific needs.
  332.  *
  333.  * CONSTRAINTS:
  334.  *   - Keys must be comparable.
  335.  */
  336. template<typename K, typename V>
  337. void mergeMapAndCompute(map<K,V>& a, map<K,V>& b, long long& answer) {
  338.     if (a.size() < b.size()) {
  339.         swap(a, b);
  340.         // When swapping, you might need to adjust the answer.
  341.         // For simplicity, this example recomputes during merge.
  342.     }
  343.     for (auto &[k, v] : b) {
  344.         answer += 1LL * v * a[k]; // Example: count equal pairs.
  345.         a[k] += v;
  346.     }
  347.     b.clear();
  348. }
  349.  
  350. /**
  351.  * PURPOSE:
  352.  *   Computes for each node the number of equal-value pairs in its subtree
  353.  *   by merging maps from children into the parent.
  354.  *
  355.  * HOW TO USE:
  356.  *   1. Create an instance: TreeMerger solver(n);
  357.  *   2. Add edges with solver.addEdge(u, v).
  358.  *   3. Call solver.dfs(0, -1).
  359.  *   4. Results are in solver.ans[u] for each node u.
  360.  *
  361.  * TIME COMPLEXITY:
  362.  *   O(n log^2 n) in worst case, but often O(n log n) with small-to-large.
  363.  *
  364.  * NOTES:
  365.  *   - This uses the small-to-large merging technique on maps.
  366.  *   - The value of each node is its index (u) in this example.
  367.  *   - You can change the logic to compute other things (e.g., sum, GCD).
  368.  *
  369.  * CONSTRAINTS:
  370.  *   - n must be at least 1.
  371.  *   - Node IDs from 0 to n-1.
  372.  */
  373. struct TreeMerger {
  374.     int n;
  375.     vector<vector<int>> adj;
  376.     vector<map<int,int>> mp;
  377.     vector<long long> ans;
  378.  
  379.     TreeMerger(int n) : n(n), adj(n), mp(n), ans(n, 0) {}
  380.  
  381.     void addEdge(int u, int v) {
  382.         adj[u].push_back(v);
  383.         adj[v].push_back(u);
  384.     }
  385.  
  386.     void dfs(int u, int p) {
  387.         mp[u][u] = 1; // Example: value of node is its ID.
  388.         for (int v : adj[u]) {
  389.             if (v == p) continue;
  390.             dfs(v, u);
  391.             // Ensure mp[u] is the larger map.
  392.             if (mp[u].size() < mp[v].size()) {
  393.                 swap(mp[u], mp[v]);
  394.                 // We need to accumulate the answer from the child.
  395.                 // Since we swapped, the child's answer is now in mp[v]? No,
  396.                 // ans[v] is the answer for the child. We'll add it later.
  397.             }
  398.             // Merge mp[v] into mp[u] and update answer for u.
  399.             for (auto &[val, cnt] : mp[v]) {
  400.                 ans[u] += 1LL * cnt * mp[u][val]; // New equal pairs.
  401.                 mp[u][val] += cnt;
  402.             }
  403.             // Add the child's answer to the parent's answer.
  404.             ans[u] += ans[v];
  405.         }
  406.     }
  407. };
  408.  
  409. // ==========================================================
  410. // 4) Advanced techniques: Offline Queries
  411. // ==========================================================
  412.  
  413. /**
  414.  * PURPOSE:
  415.  *   Handles subtree queries offline using DSU on Tree.
  416.  *   For example: "How many nodes in subtree of u have value > k?"
  417.  *
  418.  * HOW TO USE:
  419.  *   1. Create an instance: DSUonTreeWithQueries solver(n);
  420.  *   2. Add edges with solver.addEdge(u, v).
  421.  *   3. Set values for each node in solver.values[u].
  422.  *   4. Add queries using solver.addQuery(u, queryID, k).
  423.  *   5. Call solver.solve().
  424.  *   6. Answers are in solver.ans[queryID].
  425.  *
  426.  * TIME COMPLEXITY:
  427.  *   O((n + q) log^2 n) or O((n + q) log n) depending on the data structure used.
  428.  *
  429.  * NOTES:
  430.  *   - This uses a Fenwick tree (BIT) to count values.
  431.  *   - The BIT is updated when nodes are added or removed.
  432.  *   - "Offline" means all queries are known in advance.
  433.  *   - The query ID is used to store the answer in the correct order.
  434.  *
  435.  * CONSTRAINTS:
  436.  *   - Values should be within the range of the BIT (1..n).
  437.  *   - Node IDs from 0 to n-1.
  438.  *   - Query IDs from 0 to q-1.
  439.  */
  440. struct DSUonTreeWithQueries {
  441.     struct Query {
  442.         int id;
  443.         int k;
  444.     };
  445.     int n;
  446.     vector<vector<int>> adj;
  447.     vector<vector<Query>> queries;
  448.     vector<int> ans;
  449.     vector<int> values;
  450.     vector<int> bit;
  451.  
  452.     DSUonTreeWithQueries(int n) : n(n), adj(n), queries(n), ans(0), values(n), bit(n+2, 0) {}
  453.  
  454.     void addEdge(int u, int v) {
  455.         adj[u].push_back(v);
  456.         adj[v].push_back(u);
  457.     }
  458.  
  459.     void addQuery(int u, int id, int k) {
  460.         queries[u].push_back({id, k});
  461.         if ((int)ans.size() <= id) ans.resize(id + 1);
  462.     }
  463.  
  464.     // Fenwick tree update.
  465.     void updateBIT(int idx, int delta) {
  466.         for (int i = idx; i < (int)bit.size(); i += i & -i)
  467.             bit[i] += delta;
  468.     }
  469.  
  470.     // Fenwick tree query (prefix sum).
  471.     int queryBIT(int idx) {
  472.         int res = 0;
  473.         for (int i = idx; i > 0; i -= i & -i)
  474.             res += bit[i];
  475.         return res;
  476.     }
  477.  
  478.     void addNode(int u, int p, int delta) {
  479.         int val = values[u];
  480.         if (val >= 1 && val < (int)bit.size()) {
  481.             updateBIT(val, delta);
  482.         }
  483.         for (int v : adj[u]) {
  484.             if (v == p) continue;
  485.             addNode(v, u, delta);
  486.         }
  487.     }
  488.  
  489.     void answerQueries(int u) {
  490.         int total = queryBIT(n); // Total nodes currently in BIT.
  491.         for (auto &q : queries[u]) {
  492.             int le = queryBIT(q.k);
  493.             ans[q.id] = total - le;
  494.         }
  495.     }
  496.  
  497.     vector<int> sz, heavy;
  498.     void dfsSize(int u, int p) {
  499.         sz[u] = 1;
  500.         int mx = 0;
  501.         for (int v : adj[u]) {
  502.             if (v == p) continue;
  503.             dfsSize(v, u);
  504.             sz[u] += sz[v];
  505.             if (sz[v] > mx) {
  506.                 mx = sz[v];
  507.                 heavy[u] = v;
  508.             }
  509.         }
  510.     }
  511.  
  512.     void dfs(int u, int p, bool keep) {
  513.         for (int v : adj[u]) {
  514.             if (v == p || v == heavy[u]) continue;
  515.             dfs(v, u, false);
  516.         }
  517.         if (heavy[u] != -1) {
  518.             dfs(heavy[u], u, true);
  519.         }
  520.         for (int v : adj[u]) {
  521.             if (v == p || v == heavy[u]) continue;
  522.             addNode(v, u, +1);
  523.         }
  524.         addNode(u, p, +1);
  525.  
  526.         answerQueries(u);
  527.  
  528.         if (!keep) {
  529.             addNode(u, p, -1);
  530.         }
  531.     }
  532.  
  533.     void solve() {
  534.         sz.assign(n, 1);
  535.         heavy.assign(n, -1);
  536.         dfsSize(0, -1);
  537.         dfs(0, -1, false);
  538.     }
  539. };
  540.  
  541. // ==========================================================
  542. // 5) Examples of common problems using Small-to-Large
  543. // ==========================================================
  544.  
  545. /**
  546.  * PURPOSE:
  547.  *   Computes the Mex (minimum excluded non-negative integer) for each subtree.
  548.  *
  549.  * HOW TO USE:
  550.  *   1. Create an instance: MexDSU solver(n);
  551.  *   2. Add edges with solver.addEdge(u, v).
  552.  *   3. Call solver.solve().
  553.  *   4. Results in solver.ans[u] for each node u.
  554.  *
  555.  * TIME COMPLEXITY:
  556.  *   O(n log n) or O(n log^2 n) depending on the implementation.
  557.  *
  558.  * NOTES:
  559.  *   - "Mex" is the smallest non-negative integer not present in the subtree.
  560.  *   - The example uses a simplistic approach that may be slow for mex updates.
  561.  *   - A better approach uses a set of missing values, but this shows the idea.
  562.  *
  563.  * CONSTRAINTS:
  564.  *   - Node values should be in a reasonable range (0..n in this example).
  565.  */
  566. struct MexDSU {
  567.     int n;
  568.     vector<vector<int>> adj;
  569.     vector<int> sz, heavy, ans;
  570.     vector<int> freq;
  571.     int mex = 0;
  572.  
  573.     MexDSU(int n) : n(n), adj(n), sz(n), heavy(n, -1), ans(n), freq(n+2, 0) {}
  574.  
  575.     void addEdge(int u, int v) {
  576.         adj[u].push_back(v);
  577.         adj[v].push_back(u);
  578.     }
  579.  
  580.     void addNode(int u, int p, int delta) {
  581.         int val = u; // Example: value = node ID.
  582.         if (delta == 1) {
  583.             freq[val]++;
  584.         } else {
  585.             freq[val]--;
  586.         }
  587.         // Update mex. This is a simple but potentially slow method.
  588.         while (freq[mex] > 0) mex++;
  589.         // When removing, mex might decrease; a proper implementation would
  590.         // maintain a set of missing values.
  591.         for (int v : adj[u]) {
  592.             if (v == p) continue;
  593.             addNode(v, u, delta);
  594.         }
  595.     }
  596.  
  597.     void addSubtree(int u, int p, int delta) {
  598.         addNode(u, p, delta);
  599.     }
  600.  
  601.     void dfsSize(int u, int p) {
  602.         sz[u] = 1;
  603.         int mx = 0;
  604.         for (int v : adj[u]) {
  605.             if (v == p) continue;
  606.             dfsSize(v, u);
  607.             sz[u] += sz[v];
  608.             if (sz[v] > mx) {
  609.                 mx = sz[v];
  610.                 heavy[u] = v;
  611.             }
  612.         }
  613.     }
  614.  
  615.     void dfs(int u, int p, bool keep) {
  616.         for (int v : adj[u]) {
  617.             if (v == p || v == heavy[u]) continue;
  618.             dfs(v, u, false);
  619.         }
  620.         if (heavy[u] != -1) {
  621.             dfs(heavy[u], u, true);
  622.         }
  623.         for (int v : adj[u]) {
  624.             if (v == p || v == heavy[u]) continue;
  625.             addSubtree(v, u, +1);
  626.         }
  627.         addNode(u, p, +1);
  628.  
  629.         ans[u] = mex;
  630.  
  631.         if (!keep) {
  632.             addSubtree(u, p, -1);
  633.         }
  634.     }
  635.  
  636.     void solve() {
  637.         dfsSize(0, -1);
  638.         dfs(0, -1, false);
  639.     }
  640. };
  641.  
  642. // ==========================================================
  643. // 6) Extra function: Merge Multiset (add/remove)
  644. // ==========================================================
  645.  
  646. /**
  647.  * PURPOSE:
  648.  *   Merges two multisets by inserting all elements from b into a.
  649.  *   After merging, a contains all elements from both, and b is cleared.
  650.  *
  651.  * HOW TO USE:
  652.  *   Call mergeMultiset(a, b) where:
  653.  *   - a: the primary multiset (will hold the final merged result)
  654.  *   - b: the multiset to merge into a (will be emptied)
  655.  *
  656.  * TIME COMPLEXITY:
  657.  *   O(size_of_smaller_multiset * log(size_of_larger_multiset)).
  658.  *
  659.  * NOTES:
  660.  *   - The function ensures that the larger multiset is the one kept.
  661.  *   - Duplicates are preserved (multiset allows duplicates).
  662.  *
  663.  * CONSTRAINTS:
  664.  *   - Elements must be comparable.
  665.  */
  666. template<typename T>
  667. void mergeMultiset(multiset<T>& a, multiset<T>& b) {
  668.     if (a.size() < b.size()) a.swap(b);
  669.     a.insert(b.begin(), b.end());
  670.     b.clear();
  671. }
  672.  
  673. // ==========================================================
  674. // 7) Merge while keeping unique elements (Union)
  675. // ==========================================================
  676.  
  677. /**
  678.  * PURPOSE:
  679.  *   Merges two unordered_sets by inserting all unique elements from b into a.
  680.  *   After merging, a contains the union of both sets, and b is cleared.
  681.  *
  682.  * HOW TO USE:
  683.  *   Call mergeUnorderedSet(a, b) where:
  684.  *   - a: the primary unordered_set (will hold the union)
  685.  *   - b: the unordered_set to merge into a (will be emptied)
  686.  *
  687.  * TIME COMPLEXITY:
  688.  *   O(size_of_smaller_set) on average.
  689.  *
  690.  * NOTES:
  691.  *   - The function ensures that the larger set is the one kept.
  692.  *   - Duplicates are automatically removed because unordered_set stores only
  693.  *     unique elements.
  694.  *
  695.  * CONSTRAINTS:
  696.  *   - Elements must be hashable (for unordered_set).
  697.  */
  698. template<typename T>
  699. void mergeUnorderedSet(unordered_set<T>& a, unordered_set<T>& b) {
  700.     if (a.size() < b.size()) a.swap(b);
  701.     for (auto &x : b) a.insert(x);
  702.     b.clear();
  703. }
  704.  
  705. // ==========================================================
  706. // 8) Merge Vectors with sorting (to reduce complexity)
  707. // ==========================================================
  708.  
  709. /**
  710.  * PURPOSE:
  711.  *   Merges two sorted vectors into one sorted vector.
  712.  *
  713.  * HOW TO USE:
  714.  *   Call mergeSortedVectors(a, b) where a and b are sorted vectors.
  715.  *   It returns a new vector containing all elements from both, sorted.
  716.  *
  717.  * TIME COMPLEXITY:
  718.  *   O(|a| + |b|).
  719.  *
  720.  * NOTES:
  721.  *   - Both input vectors MUST be sorted in non-decreasing order.
  722.  *   - The result is a new vector; the original vectors are unchanged.
  723.  *
  724.  * CONSTRAINTS:
  725.  *   - Elements must be comparable.
  726.  */
  727. template<typename T>
  728. vector<T> mergeSortedVectors(const vector<T>& a, const vector<T>& b) {
  729.     vector<T> res;
  730.     res.reserve(a.size() + b.size());
  731.     merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(res));
  732.     return res;
  733. }
  734.  
  735. // ==========================================================
  736. // 9) Example of merging maps to count equal pairs (improved version)
  737. // ==========================================================
  738.  
  739. /**
  740.  * PURPOSE:
  741.  *   Computes the number of equal-value pairs in each subtree.
  742.  *   This is a specialized version of TreeMerger.
  743.  *
  744.  * HOW TO USE:
  745.  *   1. Create an instance: TreeMapMerger solver(n);
  746.  *   2. Add edges with solver.addEdge(u, v).
  747.  *   3. Call solver.dfs(0, -1).
  748.  *   4. Results in solver.ans[u] for each node u.
  749.  *
  750.  * TIME COMPLEXITY:
  751.  *   O(n log n) on average.
  752.  *
  753.  * NOTES:
  754.  *   - This version correctly handles the accumulation of answers from children.
  755.  *   - It uses map merging to combine data.
  756.  *
  757.  * CONSTRAINTS:
  758.  *   - Node IDs from 0 to n-1.
  759.  */
  760. struct TreeMapMerger {
  761.     int n;
  762.     vector<vector<int>> adj;
  763.     vector<map<int, int>> mp;
  764.     vector<long long> ans;
  765.  
  766.     TreeMapMerger(int n) : n(n), adj(n), mp(n), ans(n, 0) {}
  767.  
  768.     void addEdge(int u, int v) {
  769.         adj[u].push_back(v);
  770.         adj[v].push_back(u);
  771.     }
  772.  
  773.     void dfs(int u, int p) {
  774.         mp[u][u] = 1; // Example: value of node is its ID.
  775.         for (int v : adj[u]) {
  776.             if (v == p) continue;
  777.             dfs(v, u);
  778.  
  779.             // Merge the smaller map into the larger one.
  780.             if (mp[u].size() < mp[v].size()) {
  781.                 swap(mp[u], mp[v]);
  782.                 // When swapping, the answer of u might need to be adjusted.
  783.                 // We'll recompute by merging all child maps.
  784.                 // For simplicity, we accumulate ans[u] += ans[v] after merging.
  785.             }
  786.  
  787.             // Merge mp[v] into mp[u].
  788.             for (auto &[val, cnt] : mp[v]) {
  789.                 ans[u] += 1LL * cnt * mp[u][val];
  790.                 mp[u][val] += cnt;
  791.             }
  792.  
  793.             // Add the child's answer to the parent's answer.
  794.             ans[u] += ans[v];
  795.         }
  796.     }
  797. };
  798.  
  799. // ==========================================================
  800. // 10) DSU (Union-Find) with Small-To-Large to store elements of each component
  801. // ==========================================================
  802.  
  803. /**
  804.  * PURPOSE:
  805.  *   Disjoint Set Union (DSU) with small-to-large merging of element lists.
  806.  *   This allows you to maintain a list of all elements in each component.
  807.  *
  808.  * HOW TO USE:
  809.  *   1. Create an instance: DSU dsu(n);
  810.  *   2. Call dsu.unite(a, b) to merge components.
  811.  *   3. Access elements of a component via dsu.elements[dsu.find(root)].
  812.  *
  813.  * TIME COMPLEXITY:
  814.  *   O(n log n) for all union operations due to small-to-large.
  815.  *
  816.  * NOTES:
  817.  *   - "Component" means a set of connected nodes.
  818.  *   - This is useful when you need to iterate over all elements of a component
  819.  *     after merges.
  820.  *   - The elements of a component are stored in a vector.
  821.  *
  822.  * CONSTRAINTS:
  823.  *   - Node IDs from 0 to n-1.
  824.  */
  825. struct DSU {
  826.     vector<int> parent, sz;
  827.     vector<vector<int>> elements;
  828.  
  829.     DSU(int n) : parent(n), sz(n, 1), elements(n) {
  830.         iota(parent.begin(), parent.end(), 0);
  831.         for (int i = 0; i < n; i++) elements[i].push_back(i);
  832.     }
  833.  
  834.     int find(int x) {
  835.         if (parent[x] == x) return x;
  836.         return parent[x] = find(parent[x]);
  837.     }
  838.  
  839.     void unite(int a, int b) {
  840.         a = find(a);
  841.         b = find(b);
  842.         if (a == b) return;
  843.  
  844.         // Merge the smaller component into the larger one.
  845.         if (sz[a] < sz[b]) swap(a, b);
  846.  
  847.         // Move all elements from b to a.
  848.         for (int x : elements[b]) {
  849.             elements[a].push_back(x);
  850.         }
  851.         elements[b].clear();
  852.  
  853.         parent[b] = a;
  854.         sz[a] += sz[b];
  855.     }
  856. };
  857.  
  858. // ==========================================================
  859. // 11) Merging Multisets in the tree (using pointers)
  860. // ==========================================================
  861.  
  862. /**
  863.  * PURPOSE:
  864.  *   Computes answers for each node using a multiset of values in its subtree.
  865.  *   For example, you can find the maximum value in each subtree.
  866.  *
  867.  * HOW TO USE:
  868.  *   1. Create a vector of multiset pointers: vector<multiset<int>*> ms(n);
  869.  *   2. In your DFS, implement the logic as shown below.
  870.  *   3. After processing node u, ms[u] contains all values in its subtree.
  871.  *
  872.  * TIME COMPLEXITY:
  873.  *   O(n log n) overall.
  874.  *
  875.  * NOTES:
  876.  *   - Uses pointers to avoid copying large multisets.
  877.  *   - The heavy child's multiset is reused by the parent.
  878.  *   - After merging, the child's multiset is deleted to free memory.
  879.  *
  880.  * CONSTRAINTS:
  881.  *   - The tree must be processed in a DFS.
  882.  */
  883. vector<multiset<int>*> ms;
  884.  
  885. void dfsMultiset(int u, int p, vector<vector<int>>& adj) {
  886.     int bigChild = -1;
  887.     for (int v : adj[u]) {
  888.         if (v == p) continue;
  889.         dfsMultiset(v, u, adj);
  890.         if (bigChild == -1 || ms[bigChild]->size() < ms[v]->size())
  891.             bigChild = v;
  892.     }
  893.  
  894.     if (bigChild == -1) ms[u] = new multiset<int>();
  895.     else ms[u] = ms[bigChild];
  896.  
  897.     ms[u]->insert(u); // Add the value of the current node.
  898.  
  899.     for (int v : adj[u]) {
  900.         if (v == p || v == bigChild) continue;
  901.         // Merge all elements from the small multiset into the large one.
  902.         ms[u]->insert(ms[v]->begin(), ms[v]->end());
  903.         delete ms[v];
  904.     }
  905.  
  906.     // Now ms[u] contains all values in the subtree of u.
  907.     // You can answer queries for node u here.
  908. }
  909.  
  910. // ==========================================================
  911. // 12) "Clear" technique to empty large containers
  912. // ==========================================================
  913.  
  914. /**
  915.  * PURPOSE:
  916.  *   Efficiently clears a vector and releases its memory.
  917.  *
  918.  * HOW TO USE:
  919.  *   vector<T>().swap(myVec);
  920.  *
  921.  * TIME COMPLEXITY:
  922.  *   O(size_of_vector).
  923.  *
  924.  * NOTES:
  925.  *   - This is a common trick to force immediate memory deallocation.
  926.  *   - Using myVec.clear() only destroys elements but may keep the capacity.
  927.  */
  928. // Example: vector<int>().swap(myVec);
  929.  
  930. // ==========================================================
  931. // 13) Example: Calculate GCD for each subtree using map merging
  932. // ==========================================================
  933.  
  934. /**
  935.  * PURPOSE:
  936.  *   Computes the GCD of all values in each subtree.
  937.  *
  938.  * HOW TO USE:
  939.  *   Adapt the TreeMerger or DSUonTree structure to store GCD values.
  940.  *   For example, you can store a map of value frequencies and compute GCD.
  941.  *
  942.  * NOTES:
  943.  *   - GCD is associative, so you can merge results from children.
  944.  *   - This is just a conceptual example; actual implementation depends on the
  945.  *     specific problem.
  946.  */
  947.  
  948. // ==========================================================
  949. // 14) Divide & Conquer with Small-To-Large
  950. // ==========================================================
  951.  
  952. /**
  953.  * PURPOSE:
  954.  *   Solves range queries on an array using Divide and Conquer combined with
  955.  *   small-to-large optimization.
  956.  *
  957.  * HOW TO USE:
  958.  *   Implement a recursive function solve(l, r) that processes the range [l, r].
  959.  *   Find the index of the maximum (or minimum) element in the range.
  960.  *   Recurse on the left and right subranges, then process subarrays that cross
  961.  *   the pivot. Use small-to-large to iterate over the smaller side.
  962.  *
  963.  * TIME COMPLEXITY:
  964.  *   O(n log n) on average.
  965.  *
  966.  * NOTES:
  967.  *   - This technique is useful for problems that require counting subarrays
  968.  *     with certain properties (e.g., where the maximum is at a certain position).
  969.  *   - The pivot is typically the maximum or minimum element.
  970.  *   - You need a data structure (like a map) to answer queries quickly.
  971.  */
  972. long long ansDnC = 0;
  973. vector<int> a, pref; // Array and prefix sum.
  974.  
  975. void solveDnC(int l, int r) {
  976.     if (l > r) return;
  977.     if (l == r) {
  978.         // Handle single element case.
  979.         // Example: if a[l] == X && a[l] == S, ansDnC++;
  980.         return;
  981.     }
  982.  
  983.     // Find index of the maximum element in [l, r].
  984.     int idx = l;
  985.     for (int i = l; i <= r; i++) {
  986.         if (a[i] > a[idx]) idx = i;
  987.     }
  988.  
  989.     // Recurse on left and right subranges.
  990.     solveDnC(l, idx - 1);
  991.     solveDnC(idx + 1, r);
  992.  
  993.     // Count subarrays that cross idx.
  994.     if (idx - l < r - idx) {
  995.         // Left side is smaller: iterate over left side.
  996.         for (int i = l; i <= idx; i++) {
  997.             // Use a data structure (e.g., map) from the right side to count.
  998.             // Example: ansDnC += mp[need];
  999.         }
  1000.     } else {
  1001.         // Right side is smaller: iterate over right side.
  1002.         for (int i = idx; i <= r; i++) {
  1003.             // Use a data structure from the left side.
  1004.         }
  1005.     }
  1006. }
  1007.  
  1008. // ==========================================================
  1009. // 15) Optimized unordered_map merge
  1010. // ==========================================================
  1011.  
  1012. /**
  1013.  * PURPOSE:
  1014.  *   Merges two unordered_maps with improved performance by reserving space
  1015.  *   before insertion.
  1016.  *
  1017.  * HOW TO USE:
  1018.  *   Call mergeUnorderedMapOptimized(a, b) where:
  1019.  *   - a: the primary unordered_map (will hold the final result)
  1020.  *   - b: the unordered_map to merge into a (will be emptied)
  1021.  *
  1022.  * TIME COMPLEXITY:
  1023.  *   O(size_of_smaller_map) on average.
  1024.  *
  1025.  * NOTES:
  1026.  *   - Reserves space in a to avoid rehashing during insertion.
  1027.  *   - This can significantly improve performance for large maps.
  1028.  *
  1029.  * CONSTRAINTS:
  1030.  *   - Keys must be hashable.
  1031.  */
  1032. template<typename K, typename V>
  1033. void mergeUnorderedMapOptimized(unordered_map<K,V>& a, unordered_map<K,V>& b) {
  1034.     if (a.size() < b.size()) {
  1035.         a.swap(b);
  1036.     }
  1037.     a.reserve(a.size() + b.size());
  1038.     for (auto &p : b) {
  1039.         a[p.first] += p.second; // Or any other merge logic.
  1040.     }
  1041.     b.clear();
  1042. }
  1043.  
  1044. // ==========================================================
  1045. // Conclusion: Use these tools wisely, and remember that Small-to-Large
  1046. // is a powerful technique for solving tree problems in contests.
  1047. // ==========================================================
  1048.  
  1049. int main() {
  1050.     ios::sync_with_stdio(false);
  1051.     cin.tie(nullptr);
  1052.  
  1053.     // Example usage:
  1054.     // DSUonTree solver(n);
  1055.     // ... add edges ...
  1056.     // solver.solve();
  1057.  
  1058.     return 0;
  1059. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7amdWL
language:
C++ (gcc 8.3)
created:
2 days 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!