fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ===================================================================
  5. // This file contains a collection of algorithms based on the
  6. // Persistent Binary Trie (also known as Persistent 01-Trie).
  7. // Each function is ready to be used as a "black box".
  8. // Read the comments above each one to understand:
  9. //   - What it solves
  10. //   - What input it expects
  11. //   - What it returns
  12. //   - Time complexity
  13. //   - Important constraints / assumptions
  14. // ===================================================================
  15.  
  16. // ===================================================================
  17. // 1) Core Structure: Persistent Binary Trie
  18. //    This is the underlying data structure used by all the functions
  19. //    below. It supports creating new versions by inserting numbers and
  20. //    allows querying a specific version for XOR-related problems.
  21. //    The number of bits is fixed at compile time via MAX_LOG.
  22. // ===================================================================
  23.  
  24. // 1.1) Persistent Binary Trie Node and Class
  25. //      Parameters:
  26. //        - MAX_LOG: The number of bits to consider (e.g., 30 for 32-bit integers).
  27. //                   All numbers inserted must fit within these bits.
  28. //      Returns:
  29. //        - An object that can be used to build versions and answer queries.
  30. //      Time complexity: O(MAX_LOG) per insertion or query.
  31. //      Constraint: The class must be instantiated with a suitable MAX_LOG.
  32. //      Note: This is the core structure; you don't call it directly,
  33. //            but the functions below use it.
  34. template<int MAX_LOG>
  35. struct PersistentBinaryTrie {
  36.     struct Node {
  37.         int child[2]; // child[0] for bit 0, child[1] for bit 1
  38.         int cnt;      // number of numbers in this subtree
  39.         Node() {
  40.             child[0] = child[1] = 0;
  41.             cnt = 0;
  42.         }
  43.     };
  44.  
  45.     vector<Node> tree; // array of nodes
  46.     vector<int> root;  // root node index for each version
  47.     int versionCount;  // number of versions created
  48.  
  49.     PersistentBinaryTrie() {
  50.         tree.reserve(5000000); // reserve memory to avoid reallocation
  51.         tree.push_back(Node()); // node 0 is the null node
  52.         root.push_back(0);      // version 0 is empty
  53.         versionCount = 0;
  54.     }
  55.  
  56.     // Insert a number 'num' into the trie, creating a new version.
  57.     // Returns the index of the new root.
  58.     int insert(int prevRoot, int num) {
  59.         int newRoot = tree.size();
  60.         tree.push_back(tree[prevRoot]); // copy the previous root
  61.         int cur = newRoot;
  62.         int prev = prevRoot;
  63.         tree[cur].cnt++;
  64.  
  65.         for (int bit = MAX_LOG; bit >= 0; bit--) {
  66.             int b = (num >> bit) & 1;
  67.             // Create a new node for the child
  68.             int newChild = tree.size();
  69.             tree.push_back(tree[tree[prev].child[b]]);
  70.             tree[cur].child[b] = newChild;
  71.             tree[newChild].cnt++;
  72.  
  73.             // Move to the next level
  74.             cur = newChild;
  75.             prev = tree[prev].child[b];
  76.         }
  77.         return newRoot;
  78.     }
  79.  
  80.     // Query the maximum XOR of 'num' with any number in a specific version.
  81.     int queryMaxXor(int rootIdx, int num) {
  82.         int cur = rootIdx;
  83.         int ans = 0;
  84.         for (int bit = MAX_LOG; bit >= 0; bit--) {
  85.             int b = (num >> bit) & 1;
  86.             // Prefer the opposite bit to maximize XOR
  87.             if (tree[tree[cur].child[b ^ 1]].cnt > 0) {
  88.                 ans |= (1 << bit);
  89.                 cur = tree[cur].child[b ^ 1];
  90.             } else {
  91.                 cur = tree[cur].child[b];
  92.             }
  93.         }
  94.         return ans;
  95.     }
  96.  
  97.     // Query the minimum XOR of 'num' with any number in a specific version.
  98.     int queryMinXor(int rootIdx, int num) {
  99.         int cur = rootIdx;
  100.         int ans = 0;
  101.         for (int bit = MAX_LOG; bit >= 0; bit--) {
  102.             int b = (num >> bit) & 1;
  103.             // Prefer the same bit to minimize XOR
  104.             if (tree[tree[cur].child[b]].cnt > 0) {
  105.                 cur = tree[cur].child[b];
  106.             } else {
  107.                 ans |= (1 << bit);
  108.                 cur = tree[cur].child[b ^ 1];
  109.             }
  110.         }
  111.         return ans;
  112.     }
  113.  
  114.     // Get the root index of a specific version.
  115.     int getRoot(int version) {
  116.         return root[version];
  117.     }
  118.  
  119.     // Add a new version by inserting a number.
  120.     int addVersion(int num) {
  121.         int newRoot = insert(root.back(), num);
  122.         root.push_back(newRoot);
  123.         versionCount++;
  124.         return versionCount;
  125.     }
  126. };
  127.  
  128. // ===================================================================
  129. // 2) Basic Operations: Insert and Query
  130. //    These functions provide a simple interface for the most common
  131. //    tasks: inserting numbers into the trie and querying for max/min XOR.
  132. // ===================================================================
  133.  
  134. // 2.1) Insert a number into the trie and create a new version.
  135. //      Parameters:
  136. //        - trie: a PersistentBinaryTrie object
  137. //        - num: the integer to insert
  138. //      Returns:
  139. //        - the version number of the newly created version.
  140. //      Time complexity: O(MAX_LOG)
  141. //      Constraint: num must be representable within MAX_LOG bits.
  142. //      Note: This is the primary way to build the trie.
  143. int insertNumber(PersistentBinaryTrie<30>& trie, int num) {
  144.     return trie.addVersion(num);
  145. }
  146.  
  147. // 2.2) Query the maximum XOR of a number with any number in a given version.
  148. //      Parameters:
  149. //        - trie: a PersistentBinaryTrie object
  150. //        - version: the version to query (0-indexed)
  151. //        - num: the number to XOR with
  152. //      Returns:
  153. //        - the maximum possible XOR value.
  154. //      Time complexity: O(MAX_LOG)
  155. //      Constraint: version must be a valid version number.
  156. //      Note: This is used to answer queries like "what is the max XOR in a prefix".
  157. int queryMaxXorInVersion(PersistentBinaryTrie<30>& trie, int version, int num) {
  158.     return trie.queryMaxXor(trie.getRoot(version), num);
  159. }
  160.  
  161. // 2.3) Query the minimum XOR of a number with any number in a given version.
  162. //      Parameters:
  163. //        - trie: a PersistentBinaryTrie object
  164. //        - version: the version to query (0-indexed)
  165. //        - num: the number to XOR with
  166. //      Returns:
  167. //        - the minimum possible XOR value.
  168. //      Time complexity: O(MAX_LOG)
  169. //      Constraint: version must be a valid version number.
  170. //      Note: This is useful for problems asking for the minimum XOR.
  171. int queryMinXorInVersion(PersistentBinaryTrie<30>& trie, int version, int num) {
  172.     return trie.queryMinXor(trie.getRoot(version), num);
  173. }
  174.  
  175. // ===================================================================
  176. // 3) Range Queries: Query on a subarray [L, R]
  177. //    These functions use two versions to represent a range of indices.
  178. //    The range is defined by versions L-1 and R.
  179. // ===================================================================
  180.  
  181. // 3.1) Query the maximum XOR of a number with any number in a subarray [L, R].
  182. //      Parameters:
  183. //        - trie: a PersistentBinaryTrie object
  184. //        - L, R: the range of indices (1-indexed, inclusive)
  185. //        - num: the number to XOR with
  186. //      Returns:
  187. //        - the maximum XOR value achievable with any element in a[L..R].
  188. //      Time complexity: O(MAX_LOG)
  189. //      Constraint: L <= R, and versions L-1 and R must exist.
  190. //      Note: This is the most common use case for Persistent Trie.
  191. //            It works by subtracting the counts of two versions.
  192. int queryMaxXorInRange(PersistentBinaryTrie<30>& trie, int L, int R, int num) {
  193.     int rootR = trie.getRoot(R);
  194.     int rootL = trie.getRoot(L - 1);
  195.     // We traverse both roots simultaneously.
  196.     // The difference in counts tells us if a path exists in the range.
  197.     int curR = rootR, curL = rootL;
  198.     int ans = 0;
  199.     for (int bit = 30; bit >= 0; bit--) {
  200.         int b = (num >> bit) & 1;
  201.         int opposite = b ^ 1;
  202.         // Check if the opposite child exists in the range
  203.         if (trie.tree[trie.tree[curR].child[opposite]].cnt - trie.tree[trie.tree[curL].child[opposite]].cnt > 0) {
  204.             ans |= (1 << bit);
  205.             curR = trie.tree[curR].child[opposite];
  206.             curL = trie.tree[curL].child[opposite];
  207.         } else {
  208.             curR = trie.tree[curR].child[b];
  209.             curL = trie.tree[curL].child[b];
  210.         }
  211.     }
  212.     return ans;
  213. }
  214.  
  215. // 3.2) Query the minimum XOR of a number with any number in a subarray [L, R].
  216. //      Parameters:
  217. //        - trie: a PersistentBinaryTrie object
  218. //        - L, R: the range of indices (1-indexed, inclusive)
  219. //        - num: the number to XOR with
  220. //      Returns:
  221. //        - the minimum XOR value achievable with any element in a[L..R].
  222. //      Time complexity: O(MAX_LOG)
  223. //      Constraint: L <= R, and versions L-1 and R must exist.
  224. int queryMinXorInRange(PersistentBinaryTrie<30>& trie, int L, int R, int num) {
  225.     int rootR = trie.getRoot(R);
  226.     int rootL = trie.getRoot(L - 1);
  227.     int curR = rootR, curL = rootL;
  228.     int ans = 0;
  229.     for (int bit = 30; bit >= 0; bit--) {
  230.         int b = (num >> bit) & 1;
  231.         // Check if the same child exists in the range
  232.         if (trie.tree[trie.tree[curR].child[b]].cnt - trie.tree[trie.tree[curL].child[b]].cnt > 0) {
  233.             curR = trie.tree[curR].child[b];
  234.             curL = trie.tree[curL].child[b];
  235.         } else {
  236.             ans |= (1 << bit);
  237.             curR = trie.tree[curR].child[b ^ 1];
  238.             curL = trie.tree[curL].child[b ^ 1];
  239.         }
  240.     }
  241.     return ans;
  242. }
  243.  
  244. // ===================================================================
  245. // 4) Advanced Queries: K-th smallest XOR and Count of XORs < K
  246. //    These functions extend the basic queries to handle ordering.
  247. // ===================================================================
  248.  
  249. // 4.1) Find the K-th smallest XOR value (0-indexed) with 'num' in a range [L, R].
  250. //      Parameters:
  251. //        - trie: a PersistentBinaryTrie object
  252. //        - L, R: the range of indices (1-indexed, inclusive)
  253. //        - num: the number to XOR with
  254. //        - k: the 0-indexed order (e.g., k=0 gives the smallest XOR)
  255. //      Returns:
  256. //        - the K-th smallest XOR value.
  257. //      Time complexity: O(MAX_LOG)
  258. //      Constraint: k must be less than the number of elements in the range.
  259. //      Note: This is useful for problems asking for the K-th best XOR.
  260. int kthSmallestXorInRange(PersistentBinaryTrie<30>& trie, int L, int R, int num, int k) {
  261.     int rootR = trie.getRoot(R);
  262.     int rootL = trie.getRoot(L - 1);
  263.     int curR = rootR, curL = rootL;
  264.     int ans = 0;
  265.     for (int bit = 30; bit >= 0; bit--) {
  266.         int b = (num >> bit) & 1;
  267.         int cntSame = trie.tree[trie.tree[curR].child[b]].cnt - trie.tree[trie.tree[curL].child[b]].cnt;
  268.         // If k is in the "same bit" subtree, go there. Otherwise, go to the opposite.
  269.         if (k < cntSame) {
  270.             curR = trie.tree[curR].child[b];
  271.             curL = trie.tree[curL].child[b];
  272.         } else {
  273.             k -= cntSame;
  274.             ans |= (1 << bit);
  275.             curR = trie.tree[curR].child[b ^ 1];
  276.             curL = trie.tree[curL].child[b ^ 1];
  277.         }
  278.     }
  279.     return ans;
  280. }
  281.  
  282. // 4.2) Count the number of XORs with 'num' that are strictly less than 'limit' in a range [L, R].
  283. //      Parameters:
  284. //        - trie: a PersistentBinaryTrie object
  285. //        - L, R: the range of indices (1-indexed, inclusive)
  286. //        - num: the number to XOR with
  287. //        - limit: the upper bound (exclusive)
  288. //      Returns:
  289. //        - the count of elements in a[L..R] such that (element XOR num) < limit.
  290. //      Time complexity: O(MAX_LOG)
  291. //      Constraint: limit >= 0.
  292. //      Note: This is useful for problems involving counting pairs with XOR < K.
  293. long long countXorLessThanInRange(PersistentBinaryTrie<30>& trie, int L, int R, int num, int limit) {
  294.     int rootR = trie.getRoot(R);
  295.     int rootL = trie.getRoot(L - 1);
  296.     int curR = rootR, curL = rootL;
  297.     long long ans = 0;
  298.     for (int bit = 30; bit >= 0; bit--) {
  299.         if (curR == 0 && curL == 0) break;
  300.         int b = (num >> bit) & 1;
  301.         int limitBit = (limit >> bit) & 1;
  302.         if (limitBit == 1) {
  303.             // If limit's bit is 1, all numbers with the same bit as 'num' at this position
  304.             // will produce an XOR with 0 at this bit, which is less than limit.
  305.             // So we add their count and then continue with the opposite bit.
  306.             ans += trie.tree[trie.tree[curR].child[b]].cnt - trie.tree[trie.tree[curL].child[b]].cnt;
  307.             curR = trie.tree[curR].child[b ^ 1];
  308.             curL = trie.tree[curL].child[b ^ 1];
  309.         } else {
  310.             // If limit's bit is 0, we must continue with the same bit to stay equal so far.
  311.             curR = trie.tree[curR].child[b];
  312.             curL = trie.tree[curL].child[b];
  313.         }
  314.     }
  315.     return ans;
  316. }
  317.  
  318. // ===================================================================
  319. // 5) Tricks & Patterns that appeared in ECPC/ACPC
  320. //    Extra useful utilities for specific problem types.
  321. // ===================================================================
  322.  
  323. // 5.1) Solve "Maximum XOR Subarray" with range [L, R].
  324. //      Problem: Given an array, answer queries of the form:
  325. //      "Find max (a[p] xor a[p+1] xor ... xor a[R]) for L <= p <= R".
  326. //      Parameters:
  327. //        - prefixXor: an array where prefixXor[i] = a[1] xor ... xor a[i].
  328. //        - L, R: the range (1-indexed, inclusive).
  329. //        - x: an additional value to XOR with (often 0).
  330. //      Returns:
  331. //        - the maximum XOR value.
  332. //      Time complexity: O(MAX_LOG) per query after building the trie.
  333. //      Constraint: prefixXor must be built first, and a Persistent Trie
  334. //                   must be constructed from prefixXor.
  335. //      Note: The problem reduces to finding max (prefixXor[p-1] xor (prefixXor[R] xor x)).
  336. //            So we query the range [L-1, R-1] for the best partner.
  337. int maxSubarrayXorInRange(const vector<int>& prefixXor, PersistentBinaryTrie<30>& trie, int L, int R, int x = 0) {
  338.     int target = prefixXor[R] ^ x;
  339.     return queryMaxXorInRange(trie, L - 1, R - 1, target);
  340. }
  341.  
  342. // 5.2) Build a Persistent Trie from an array of prefix XORs.
  343. //      Parameters:
  344. //        - arr: the original array (1-indexed, but can be 0-indexed).
  345. //      Returns:
  346. //        - a PersistentBinaryTrie object containing all prefix XORs.
  347. //      Time complexity: O(n * MAX_LOG)
  348. //      Constraint: arr elements must fit in MAX_LOG bits.
  349. //      Note: This is a common setup for many XOR-related problems.
  350. PersistentBinaryTrie<30> buildPersistentTrieFromArray(const vector<int>& arr) {
  351.     PersistentBinaryTrie<30> trie;
  352.     int currentXor = 0;
  353.     trie.addVersion(currentXor); // version 0: empty, or prefix 0
  354.     for (int x : arr) {
  355.         currentXor ^= x;
  356.         trie.addVersion(currentXor);
  357.     }
  358.     return trie;
  359. }
  360.  
  361. // 5.3) Count pairs (i, j) with i < j and (a[i] xor a[j]) < K.
  362. //      This is a classic problem; the implementation below shows how to
  363. //      do it with a Persistent Trie by querying ranges for each i.
  364. //      Parameters:
  365. //        - arr: the input array.
  366. //        - K: the upper bound (exclusive).
  367. //      Returns:
  368. //        - the number of pairs with XOR < K.
  369. //      Time complexity: O(n * MAX_LOG)
  370. //      Constraint: arr elements must fit in MAX_LOG bits.
  371. //      Note: This is a placeholder; use the range version for actual counting.
  372. long long countPairsWithXorLessThanK(const vector<int>& arr, int K) {
  373.     // Not implemented directly; see countPairsWithXorLessThanKInRange.
  374.     // Provided for completeness.
  375.     return 0;
  376. }
  377.  
  378. // 5.4) Count pairs (i, j) with L <= i < j <= R and (a[i] xor a[j]) < K.
  379. //      This is a more general version of the above.
  380. //      Parameters:
  381. //        - prefixXor: the array of prefix XORs.
  382. //        - L, R: the range of indices (1-indexed, inclusive).
  383. //        - K: the upper bound (exclusive).
  384. //      Returns:
  385. //        - the number of pairs within [L, R] with XOR < K.
  386. //      Time complexity: O((R-L+1) * MAX_LOG)
  387. //      Constraint: prefixXor must be built.
  388. //      Note: This is a more advanced version that uses range queries.
  389. long long countPairsWithXorLessThanKInRange(const vector<int>& prefixXor, PersistentBinaryTrie<30>& trie, int L, int R, int K) {
  390.     long long ans = 0;
  391.     for (int i = L; i <= R; i++) {
  392.         // For each element at position i, count previous elements in [L, i-1]
  393.         // that give XOR < K with prefixXor[i].
  394.         ans += countXorLessThanInRange(trie, L, i - 1, prefixXor[i], K);
  395.     }
  396.     return ans;
  397. }
  398.  
  399. // 5.5) Find the maximum XOR of any two elements in a range [L, R].
  400. //      Parameters:
  401. //        - prefixXor: the array of prefix XORs.
  402. //        - L, R: the range (1-indexed, inclusive).
  403. //      Returns:
  404. //        - the maximum XOR value between any two elements in a[L..R].
  405. //      Time complexity: O((R-L+1) * MAX_LOG)
  406. //      Constraint: prefixXor must be built.
  407. //      Note: This is a more complex problem. For each i in [L, R], we query
  408. //            the range [L, i-1] for the max XOR with a[i].
  409. int maxXorPairInRange(const vector<int>& prefixXor, PersistentBinaryTrie<30>& trie, int L, int R) {
  410.     int ans = 0;
  411.     for (int i = L; i <= R; i++) {
  412.         ans = max(ans, queryMaxXorInRange(trie, L, i - 1, prefixXor[i]));
  413.     }
  414.     return ans;
  415. }
  416.  
  417. // ===================================================================
  418. // 6) Helper Functions
  419. // ===================================================================
  420.  
  421. // 6.1) Get the number of elements in a specific version.
  422. //      Parameters:
  423. //        - trie: a PersistentBinaryTrie object
  424. //        - version: the version number
  425. //      Returns:
  426. //        - the count of elements inserted up to that version.
  427. //      Time complexity: O(1)
  428. int getVersionSize(PersistentBinaryTrie<30>& trie, int version) {
  429.     return trie.tree[trie.getRoot(version)].cnt;
  430. }
  431.  
  432. // 6.2) Get the total number of versions created.
  433. //      Parameters:
  434. //        - trie: a PersistentBinaryTrie object
  435. //      Returns:
  436. //        - the number of versions (including version 0).
  437. //      Time complexity: O(1)
  438. int getVersionCount(PersistentBinaryTrie<30>& trie) {
  439.     return trie.root.size();
  440. }
  441.  
  442. // ===================================================================
  443. // main() with example usage
  444. // ===================================================================
  445.  
  446. int main() {
  447.     ios::sync_with_stdio(false);
  448.     cin.tie(nullptr);
  449.  
  450.     // Example 1: Basic Insert and Query
  451.     PersistentBinaryTrie<30> trie;
  452.     trie.addVersion(5);
  453.     trie.addVersion(3);
  454.     trie.addVersion(8);
  455.     // Now versions: 0: empty, 1: [5], 2: [5,3], 3: [5,3,8]
  456.  
  457.     cout << "Max XOR of 7 in version 3: " << queryMaxXorInVersion(trie, 3, 7) << '\n'; // 15 (8^7=15)
  458.     cout << "Min XOR of 7 in version 3: " << queryMinXorInVersion(trie, 3, 7) << '\n'; // 2 (5^7=2)
  459.  
  460.     // Example 2: Range Query
  461.     cout << "Max XOR of 7 in range [2, 3] (elements 3 and 8): " << queryMaxXorInRange(trie, 2, 3, 7) << '\n'; // 15 (8^7=15)
  462.     cout << "Min XOR of 7 in range [2, 3]: " << queryMinXorInRange(trie, 2, 3, 7) << '\n'; // 4 (3^7=4)
  463.  
  464.     // Example 3: K-th smallest XOR
  465.     cout << "0-th smallest XOR of 7 in range [1, 3]: " << kthSmallestXorInRange(trie, 1, 3, 7, 0) << '\n'; // 2 (5^7=2)
  466.     cout << "1-st smallest XOR of 7 in range [1, 3]: " << kthSmallestXorInRange(trie, 1, 3, 7, 1) << '\n'; // 4 (3^7=4)
  467.     cout << "2-nd smallest XOR of 7 in range [1, 3]: " << kthSmallestXorInRange(trie, 1, 3, 7, 2) << '\n'; // 15 (8^7=15)
  468.  
  469.     // Example 4: Count XORs < K
  470.     cout << "Count of XORs with 7 < 10 in range [1, 3]: " << countXorLessThanInRange(trie, 1, 3, 7, 10) << '\n'; // 2 (2 and 4)
  471.  
  472.     return 0;
  473. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max XOR of 7 in version 3: 15
Min XOR of 7 in version 3: 2
Max XOR of 7 in range [2, 3] (elements 3 and 8): 15
Min XOR of 7 in range [2, 3]: 4
0-th smallest XOR of 7 in range [1, 3]: 2
1-st smallest XOR of 7 in range [1, 3]: 4
2-nd smallest XOR of 7 in range [1, 3]: 15
Count of XORs with 7 < 10 in range [1, 3]: 2
https://ideone.com/lwIvQD
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!