fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ============================================================================
  5. //  ROLLBACK DISJOINT SET UNION (DSU) WITH UNDO
  6. // ============================================================================
  7. // PURPOSE:
  8. //   A DSU that supports rolling back the last union operations.
  9. //   It does NOT use path compression (to allow rollback), only union by size,
  10. //   so find() runs in O(log N).
  11. //
  12. // METHODS:
  13. //   - RollbackDSU(int n)         : initialise n isolated elements (0..n-1)
  14. //   - int find(int x)            : returns the root of x (no compression)
  15. //   - bool unite(int a, int b)   : merges sets of a and b; returns true if merged
  16. //   - int snapshot()             : returns a token (history size) for current state
  17. //   - void rollback(int snap)    : restores DSU to the state at snap
  18. //   - int sizeOfRoot(int x)      : returns size of the set containing x
  19. //   - int getMaxSize()           : returns maximum component size over ALL elements
  20. //
  21. // TIME COMPLEXITY:
  22. //   - find     : O(log N) (union by size)
  23. //   - unite    : O(log N)
  24. //   - rollback : O(number of undone operations * log N)
  25. //
  26. // NOTES:
  27. //   - Elements are considered isolated even if not "active" in the current range.
  28. //     Active status is managed outside (see MoRollbackSolver).
  29. //   - The history stores enough information to restore maxSize correctly.
  30. // ============================================================================
  31. class RollbackDSU {
  32. private:
  33.     vector<int> parent, sz;
  34.     struct Change {
  35.         int child;      // root that became a child
  36.         int parentRoot; // root that became the new parent
  37.         int oldMax;     // value of maxSize before this union
  38.     };
  39.     vector<Change> history;
  40.     int maxSize; // maximum component size among ALL elements (active + inactive)
  41.  
  42. public:
  43.     RollbackDSU(int n) {
  44.         parent.resize(n);
  45.         sz.assign(n, 1);
  46.         maxSize = (n > 0 ? 1 : 0);
  47.         for (int i = 0; i < n; ++i) parent[i] = i;
  48.         history.clear();
  49.     }
  50.  
  51.     int find(int x) const {
  52.         while (parent[x] != x) x = parent[x];
  53.         return x;
  54.     }
  55.  
  56.     // Returns true if a and b were in different sets (i.e., a union happened).
  57.     bool unite(int a, int b) {
  58.         a = find(a);
  59.         b = find(b);
  60.         if (a == b) return false;
  61.         if (sz[a] < sz[b]) swap(a, b); // a becomes the new root
  62.         // Save old state for rollback
  63.         history.push_back({b, a, maxSize});
  64.         parent[b] = a;
  65.         sz[a] += sz[b];
  66.         maxSize = max(maxSize, sz[a]);
  67.         return true;
  68.     }
  69.  
  70.     int snapshot() const {
  71.         return (int)history.size();
  72.     }
  73.  
  74.     void rollback(int snap) {
  75.         while ((int)history.size() > snap) {
  76.             Change ch = history.back();
  77.             history.pop_back();
  78.             parent[ch.child] = ch.child;
  79.             sz[ch.parentRoot] -= sz[ch.child];
  80.             maxSize = ch.oldMax;
  81.         }
  82.     }
  83.  
  84.     int sizeOfRoot(int x) const {
  85.         return sz[find(x)];
  86.     }
  87.  
  88.     int getMaxSize() const {
  89.         return maxSize;
  90.     }
  91. };
  92.  
  93. // ============================================================================
  94. //  QUERY STRUCTURE
  95. // ============================================================================
  96. struct Query {
  97.     int l, r, idx; // inclusive range [l, r], original index
  98. };
  99.  
  100. // ============================================================================
  101. //  MO'S ALGORITHM WITH ROLLBACK DSU – SOLVER FOR RANGE CONNECTIVITY QUERIES
  102. // ============================================================================
  103. // PURPOSE:
  104. //   Answers many queries on a static array. Each query asks for a property of
  105. //   the graph formed by elements inside [l, r] with edges between adjacent
  106. //   indices i and i+1 if they satisfy a condition (here: abs(a[i]-a[i+1]) <= K).
  107. //
  108. //   Two concrete queries are provided:
  109. //     1) Maximum connected component size inside the range.
  110. //     2) Number of connected components inside the range.
  111. //
  112. // HOW TO USE:
  113. //   1) Build your array and a vector of Query {l, r, idx}.
  114. //   2) Call maxComponentSizeInRange(arr, queries, K) or
  115. //      countComponentsInRange(arr, queries, K).
  116. //   3) The function returns a vector<int> where ans[idx] is the answer.
  117. //
  118. // TIME COMPLEXITY:
  119. //   Let N = array size, Q = number of queries, B = block size (≈ N / sqrt(Q)).
  120. //   For each block, the right pointer moves O(N), total O(N * (N/B)).
  121. //   Left-pointer additions per query cost O(B), total O(Q * B).
  122. //   With B ≈ N / sqrt(Q), total DSU operations: O((N+Q)*sqrt(N)*log N).
  123. //
  124. // CONSTRAINTS / ASSUMPTIONS:
  125. //   - Array contains integers (int is fine; change to long long if needed).
  126. //   - Queries are 0-indexed inclusive [l, r].
  127. //   - K is an integer threshold (can be negative → no edges).
  128. //   - If Q = 0, returns an empty vector.
  129. //   - The connection condition is hard‑coded as a lambda – modify it to change the problem.
  130. //
  131. // NOTES:
  132. //   - The DSU is reinitialised for each block of the MO order.
  133. //   - Only active elements (inside the current range) are considered.
  134. //   - Temporary left‑side additions are rolled back after each query.
  135. // ============================================================================
  136.  
  137. // Helper: sort queries by block of l, then by r (ascending).
  138. static vector<Query> buildBlockOrder(const vector<Query>& queries, int blockSize) {
  139.     vector<Query> qs = queries;
  140.     sort(qs.begin(), qs.end(), [&](const Query& a, const Query& b) {
  141.         int blockA = a.l / blockSize;
  142.         int blockB = b.l / blockSize;
  143.         if (blockA != blockB) return blockA < blockB;
  144.         return a.r < b.r;
  145.     });
  146.     return qs;
  147. }
  148.  
  149. // ----------------------------------------------------------------------------
  150. //  1) MAXIMUM CONNECTED COMPONENT SIZE INSIDE EACH RANGE
  151. // ----------------------------------------------------------------------------
  152. vector<int> maxComponentSizeInRange(const vector<int>& arr,
  153.                                     const vector<Query>& queries,
  154.                                     int K) {
  155.     int n = (int)arr.size();
  156.     int q = (int)queries.size();
  157.     vector<int> ans(q, 0);
  158.     if (q == 0) return ans;
  159.  
  160.     // Block size: a common choice is max(1, int(n / sqrt(q))).
  161.     // You can adjust this for performance.
  162.     int blockSize = max(1, (int)(n / max(1.0, sqrt((double)q))));
  163.  
  164.     vector<Query> ordered = buildBlockOrder(queries, blockSize);
  165.  
  166.     // active[i] == true if arr[i] is currently inside the "permanent" range
  167.     vector<char> active(n, 0);
  168.  
  169.     // DSU with rollback; initially all isolated (but inactive).
  170.     RollbackDSU dsu(n);
  171.  
  172.     // These track the state of ACTIVE components only.
  173.     int activeComps = 0;
  174.     int maxActiveSize = 0;
  175.  
  176.     // Core add operation: activate position p and connect it to active neighbours.
  177.     // It updates activeComps and maxActiveSize.
  178.     auto addCore = [&](int p) {
  179.         if (active[p]) return; // should not happen, but safety
  180.         active[p] = 1;
  181.         activeComps++;
  182.         maxActiveSize = max(maxActiveSize, 1);
  183.  
  184.         // Helper to connect p with q if q is active and the condition holds.
  185.         auto tryConnect = [&](int q) {
  186.             if (q < 0 || q >= n) return;
  187.             if (!active[q]) return;
  188.             // ---------- MODIFY THIS CONDITION FOR A DIFFERENT PROBLEM ----------
  189.             bool condition = (abs(arr[p] - arr[q]) <= K);
  190.             // -------------------------------------------------------------------
  191.             if (!condition) return;
  192.             if (dsu.find(p) == dsu.find(q)) return;
  193.             // Save current sizes for updating maxActiveSize correctly.
  194.             int szP = dsu.sizeOfRoot(p);
  195.             int szQ = dsu.sizeOfRoot(q);
  196.             if (dsu.unite(p, q)) {
  197.                 activeComps--;
  198.                 int newSize = szP + szQ;
  199.                 maxActiveSize = max(maxActiveSize, newSize);
  200.             }
  201.         };
  202.  
  203.         tryConnect(p - 1);
  204.         tryConnect(p + 1);
  205.     };
  206.  
  207.     // Snapshot of the state (history + active component stats)
  208.     struct StateSnapshot {
  209.         int histSize;
  210.         int comps;
  211.         int maxSize;
  212.     };
  213.  
  214.     auto getStateSnapshot = [&]() -> StateSnapshot {
  215.         return {dsu.snapshot(), activeComps, maxActiveSize};
  216.     };
  217.  
  218.     auto restoreState = [&](const StateSnapshot& snap) {
  219.         dsu.rollback(snap.histSize);
  220.         activeComps = snap.comps;
  221.         maxActiveSize = snap.maxSize;
  222.     };
  223.  
  224.     // Process block by block
  225.     int curBlock = -1;
  226.     int curR = -1; // permanent right pointer
  227.     int curL = -1; // permanent left pointer (used only internally)
  228.  
  229.     for (const Query& qry : ordered) {
  230.         int block = qry.l / blockSize;
  231.         if (block != curBlock) {
  232.             // New block: reset everything
  233.             curBlock = block;
  234.             // Initialise empty permanent range: (blockEnd, blockEnd]
  235.             int blockEnd = min(n - 1, (block + 1) * blockSize - 1);
  236.             curR = blockEnd;
  237.             curL = blockEnd + 1; // empty range
  238.  
  239.             // Reinitialise DSU and active array
  240.             dsu = RollbackDSU(n);
  241.             fill(active.begin(), active.end(), 0);
  242.             activeComps = 0;
  243.             maxActiveSize = 0;
  244.         }
  245.  
  246.         // Expand right pointer permanently
  247.         while (curR < qry.r) {
  248.             ++curR;
  249.             addCore(curR);
  250.         }
  251.  
  252.         // Take a snapshot before adding temporary left elements
  253.         StateSnapshot snap = getStateSnapshot();
  254.  
  255.         // Expand left pointer temporarily (we will rollback these additions)
  256.         vector<int> tempAdded;
  257.         while (curL > qry.l) {
  258.             --curL;
  259.             addCore(curL);
  260.             tempAdded.push_back(curL);
  261.         }
  262.  
  263.         // Answer the query using the current active components
  264.         ans[qry.idx] = maxActiveSize;
  265.  
  266.         // Rollback temporary left additions
  267.         restoreState(snap);
  268.         for (int p : tempAdded) {
  269.             active[p] = 0; // they are no longer in the range
  270.         }
  271.         // Reset curL to the right end of the block for the next query
  272.         int blockEnd = min(n - 1, (block + 1) * blockSize - 1);
  273.         curL = blockEnd + 1;
  274.     }
  275.  
  276.     return ans;
  277. }
  278.  
  279. // ----------------------------------------------------------------------------
  280. //  2) NUMBER OF CONNECTED COMPONENTS INSIDE EACH RANGE
  281. // ----------------------------------------------------------------------------
  282. vector<int> countComponentsInRange(const vector<int>& arr,
  283.                                    const vector<Query>& queries,
  284.                                    int K) {
  285.     int n = (int)arr.size();
  286.     int q = (int)queries.size();
  287.     vector<int> ans(q, 0);
  288.     if (q == 0) return ans;
  289.  
  290.     int blockSize = max(1, (int)(n / max(1.0, sqrt((double)q))));
  291.     vector<Query> ordered = buildBlockOrder(queries, blockSize);
  292.  
  293.     vector<char> active(n, 0);
  294.     RollbackDSU dsu(n);
  295.     int activeComps = 0;
  296.     int maxActiveSize = 0; // not used here, but needed for snapshot struct
  297.  
  298.     auto addCore = [&](int p) {
  299.         if (active[p]) return;
  300.         active[p] = 1;
  301.         activeComps++;
  302.         maxActiveSize = max(maxActiveSize, 1);
  303.  
  304.         auto tryConnect = [&](int q) {
  305.             if (q < 0 || q >= n) return;
  306.             if (!active[q]) return;
  307.             // ---------- MODIFY THIS CONDITION FOR A DIFFERENT PROBLEM ----------
  308.             bool condition = (abs(arr[p] - arr[q]) <= K);
  309.             // -------------------------------------------------------------------
  310.             if (!condition) return;
  311.             if (dsu.find(p) == dsu.find(q)) return;
  312.             if (dsu.unite(p, q)) {
  313.                 activeComps--;
  314.             }
  315.         };
  316.  
  317.         tryConnect(p - 1);
  318.         tryConnect(p + 1);
  319.     };
  320.  
  321.     struct StateSnapshot {
  322.         int histSize;
  323.         int comps;
  324.         int maxSize;
  325.     };
  326.  
  327.     auto getStateSnapshot = [&]() -> StateSnapshot {
  328.         return {dsu.snapshot(), activeComps, maxActiveSize};
  329.     };
  330.  
  331.     auto restoreState = [&](const StateSnapshot& snap) {
  332.         dsu.rollback(snap.histSize);
  333.         activeComps = snap.comps;
  334.         maxActiveSize = snap.maxSize;
  335.     };
  336.  
  337.     int curBlock = -1;
  338.     int curR = -1;
  339.     int curL = -1;
  340.  
  341.     for (const Query& qry : ordered) {
  342.         int block = qry.l / blockSize;
  343.         if (block != curBlock) {
  344.             curBlock = block;
  345.             int blockEnd = min(n - 1, (block + 1) * blockSize - 1);
  346.             curR = blockEnd;
  347.             curL = blockEnd + 1;
  348.             dsu = RollbackDSU(n);
  349.             fill(active.begin(), active.end(), 0);
  350.             activeComps = 0;
  351.             maxActiveSize = 0;
  352.         }
  353.  
  354.         while (curR < qry.r) {
  355.             ++curR;
  356.             addCore(curR);
  357.         }
  358.  
  359.         StateSnapshot snap = getStateSnapshot();
  360.         vector<int> tempAdded;
  361.         while (curL > qry.l) {
  362.             --curL;
  363.             addCore(curL);
  364.             tempAdded.push_back(curL);
  365.         }
  366.  
  367.         ans[qry.idx] = activeComps;
  368.  
  369.         restoreState(snap);
  370.         for (int p : tempAdded) {
  371.             active[p] = 0;
  372.         }
  373.         int blockEnd = min(n - 1, (block + 1) * blockSize - 1);
  374.         curL = blockEnd + 1;
  375.     }
  376.  
  377.     return ans;
  378. }
  379.  
  380. // ============================================================================
  381. //  ADVANCED TRICKS & PATTERNS FOR MO + DSU
  382. // ============================================================================
  383. // 1) Custom connection condition:
  384. //    Replace the line "bool condition = (abs(arr[p] - arr[q]) <= K);"
  385. //    inside addCore with your own logic.
  386. //
  387. // 2) MO on trees:
  388. //    Linearise the tree using Euler tour (tin/tout) and treat paths as ranges.
  389. //
  390. // 3) MO with updates (time dimension):
  391. //    Extend MO with a time pointer and use the same rollback mechanism.
  392. //
  393. // 4) Block size:
  394. //    A good starting point is max(1, int(n / sqrt(q))).
  395. //    For n,q ≤ 1e5, blockSize ≈ 450 works well in practice.
  396. // ============================================================================
  397.  
  398. // ============================================================================
  399. //  EXAMPLE USAGE (main)
  400. // ============================================================================
  401. int main() {
  402.     ios::sync_with_stdio(false);
  403.     cin.tie(nullptr);
  404.  
  405.     // Example array and queries
  406.     vector<int> arr = {10, 20, 30, 25, 15, 5};
  407.     int K = 10; // edge if |a[i] - a[i+1]| <= 10
  408.  
  409.     vector<Query> queries = {
  410.         {0, 5, 0}, // whole array
  411.         {1, 3, 1}, // [20, 30, 25]
  412.         {2, 4, 2}  // [30, 25, 15]
  413.     };
  414.  
  415.     // 1) Maximum component size
  416.     vector<int> maxSizes = maxComponentSizeInRange(arr, queries, K);
  417.     cout << "Max component sizes:\n";
  418.     for (int i = 0; i < (int)queries.size(); ++i) {
  419.         cout << "Query " << i << " [" << queries[i].l << ", " << queries[i].r
  420.              << "] : " << maxSizes[i] << "\n";
  421.     }
  422.  
  423.     // 2) Number of components
  424.     vector<int> compCounts = countComponentsInRange(arr, queries, K);
  425.     cout << "\nNumber of components:\n";
  426.     for (int i = 0; i < (int)queries.size(); ++i) {
  427.         cout << "Query " << i << " [" << queries[i].l << ", " << queries[i].r
  428.              << "] : " << compCounts[i] << "\n";
  429.     }
  430.  
  431.     return 0;
  432. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max component sizes:
Query 0 [0, 5] : 6
Query 1 [1, 3] : 3
Query 2 [2, 4] : 3

Number of components:
Query 0 [0, 5] : 1
Query 1 [1, 3] : 1
Query 2 [2, 4] : 1
https://ideone.com/UqHVq8
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!