fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ===================================================================
  5. // This file contains a collection of Binary Trie (Bitwise Trie)
  6. // algorithms. A Binary Trie is a tree where each node has up to two
  7. // children (0 and 1), representing the binary bits of integers, from
  8. // the most significant bit (MSB) down to the least significant bit.
  9. // It is used to efficiently answer queries about XOR, maximum XOR,
  10. // minimum XOR, and counting numbers with XOR constraints.
  11. //
  12. // Each function is ready to be used as a "black box". Read the
  13. // comments above each one to understand:
  14. //   - What it solves
  15. //   - What input it expects
  16. //   - What it returns
  17. //   - Time complexity
  18. //   - Important constraints / assumptions
  19. // ===================================================================
  20.  
  21. // ===================================================================
  22. // SECTION 1: Basic Binary Trie Node and Helpers
  23. // ===================================================================
  24.  
  25. // LOG is the highest bit index we care about.
  26. // For 32‑bit signed integers (up to 2^31‑1), bits 30..0 are enough.
  27. // If you use long long (up to 9e18), change LOG to 60.
  28. // IMPORTANT: Set LOG according to the maximum value you will insert.
  29. static const int LOG = 30;   // bits from LOG down to 0 inclusive
  30.  
  31. // A node in the Binary Trie.
  32. struct TrieNode {
  33.     int child[2];   // child[0] for bit 0, child[1] for bit 1
  34.     int cnt;        // how many numbers pass through this node (for counting / deletion)
  35.     TrieNode() {
  36.         child[0] = child[1] = -1;
  37.         cnt = 0;
  38.     }
  39. };
  40.  
  41. // ===================================================================
  42. // SECTION 2: Basic Binary Trie Class
  43. // ===================================================================
  44.  
  45. // This class provides the core trie operations.
  46. // It stores integers and supports:
  47. //   - insert(x)
  48. //   - erase(x)   (decrement counts, assumes x exists)
  49. //   - maxXor(x)  : maximum XOR value with any stored number
  50. //   - minXor(x)  : minimum XOR value with any stored number
  51. //   - countXorLessThan(x, limit) : how many stored numbers y satisfy (x XOR y) < limit
  52. class BinaryTrie {
  53. public:
  54.     vector<TrieNode> tr;
  55.  
  56.     BinaryTrie() {
  57.         tr.push_back(TrieNode());   // node 0 is the root
  58.     }
  59.  
  60.     // Insert a number x into the trie.
  61.     // Time: O(LOG)
  62.     void insert(int x) {
  63.         int node = 0;
  64.         tr[0].cnt++;                // increment root count
  65.         for (int bit = LOG; bit >= 0; bit--) {
  66.             int b = (x >> bit) & 1;
  67.             if (tr[node].child[b] == -1) {
  68.                 tr[node].child[b] = tr.size();
  69.                 tr.push_back(TrieNode());
  70.             }
  71.             node = tr[node].child[b];
  72.             tr[node].cnt++;
  73.         }
  74.     }
  75.  
  76.     // Erase one occurrence of x from the trie.
  77.     // Precondition: x has been inserted at least once.
  78.     // Time: O(LOG)
  79.     void erase(int x) {
  80.         int node = 0;
  81.         tr[0].cnt--;                // decrement root count
  82.         for (int bit = LOG; bit >= 0; bit--) {
  83.             int b = (x >> bit) & 1;
  84.             int nxt = tr[node].child[b];
  85.             tr[nxt].cnt--;
  86.             node = nxt;
  87.         }
  88.     }
  89.  
  90.     // Return the maximum possible XOR value between x and any number
  91.     // currently stored in the trie.
  92.     // If the trie is empty, the behaviour is undefined (will return 0).
  93.     // Time: O(LOG)
  94.     int maxXor(int x) {
  95.         int node = 0;
  96.         int ans = 0;
  97.         for (int bit = LOG; bit >= 0; bit--) {
  98.             int b = (x >> bit) & 1;
  99.             int want = b ^ 1;   // we prefer the opposite bit to get 1 in XOR
  100.             if (tr[node].child[want] != -1 && tr[tr[node].child[want]].cnt > 0) {
  101.                 ans |= (1 << bit);
  102.                 node = tr[node].child[want];
  103.             } else {
  104.                 node = tr[node].child[b];
  105.             }
  106.         }
  107.         return ans;
  108.     }
  109.  
  110.     // Return the minimum possible XOR value between x and any number
  111.     // stored in the trie.
  112.     // If the trie is empty, returns INT_MAX (you should check emptiness).
  113.     // Time: O(LOG)
  114.     int minXor(int x) {
  115.         int node = 0;
  116.         int ans = 0;
  117.         for (int bit = LOG; bit >= 0; bit--) {
  118.             int b = (x >> bit) & 1;
  119.             // try to go with the same bit to get 0 in XOR first
  120.             if (tr[node].child[b] != -1 && tr[tr[node].child[b]].cnt > 0) {
  121.                 node = tr[node].child[b];
  122.             } else {
  123.                 ans |= (1 << bit);
  124.                 node = tr[node].child[b ^ 1];
  125.             }
  126.         }
  127.         return ans;
  128.     }
  129.  
  130.     // Count how many numbers y currently in the trie satisfy (x XOR y) < limit.
  131.     // This is useful for counting pairs/subarrays with XOR less than a threshold.
  132.     // If limit <= 0, returns 0. If limit is very large, returns total count.
  133.     // Time: O(LOG)
  134.     int countXorLessThan(int x, int limit) {
  135.         if (limit <= 0) return 0;
  136.         int node = 0;
  137.         int ans = 0;
  138.         for (int bit = LOG; bit >= 0; bit--) {
  139.             if (node == -1 || tr[node].cnt == 0) break;
  140.             int xb = (x >> bit) & 1;
  141.             int lb = (limit >> bit) & 1;
  142.             // If limit has bit 1 at this position, we can take the branch
  143.             // that makes XOR bit 0 (less at this bit), and add its count.
  144.             if (lb == 1) {
  145.                 int take0 = tr[node].child[xb]; // XOR bit = 0
  146.                 if (take0 != -1 && tr[take0].cnt > 0) {
  147.                     ans += tr[take0].cnt;
  148.                 }
  149.                 // then continue with the branch that makes XOR bit = 1
  150.                 node = tr[node].child[xb ^ 1];
  151.             } else {
  152.                 // limit bit is 0, we must have XOR bit 0 to stay less
  153.                 node = tr[node].child[xb];
  154.             }
  155.         }
  156.         // At the end, if we exactly followed limit bits with XOR = 0 all the way,
  157.         // then (x XOR y) == limit, not less, so we don't add.
  158.         return ans;
  159.     }
  160.  
  161.     // Count how many numbers y satisfy (x XOR y) <= limit.
  162.     // Simply call countXorLessThan(x, limit+1) (careful with overflow).
  163.     int countXorLessEqual(int x, int limit) {
  164.         if (limit == INT_MAX) return totalCount(); // avoid overflow
  165.         return countXorLessThan(x, limit + 1);
  166.     }
  167.  
  168.     // Return the total number of elements currently stored.
  169.     int totalCount() {
  170.         return tr[0].cnt;
  171.     }
  172. };
  173.  
  174. // ===================================================================
  175. // SECTION 3: Common Queries on Arrays using Binary Trie
  176. // ===================================================================
  177.  
  178. // 3.1) Maximum XOR of any two numbers in the array.
  179. //      Parameters:
  180. //        - arr: vector of integers (can be unsorted, any values)
  181. //      Returns:
  182. //        - the maximum XOR value between any pair (i != j) in arr.
  183. //      Time complexity: O(n * LOG) where n = arr.size()
  184. //      Constraint: arr must have at least 2 elements.
  185. int maxXorPair(vector<int>& arr) {
  186.     BinaryTrie trie;
  187.     trie.insert(arr[0]);
  188.     int ans = 0;
  189.     for (int i = 1; i < (int)arr.size(); i++) {
  190.         ans = max(ans, trie.maxXor(arr[i]));
  191.         trie.insert(arr[i]);
  192.     }
  193.     return ans;
  194. }
  195.  
  196. // 3.2) Minimum XOR of any two numbers in the array (minimum pair XOR).
  197. //      Parameters:
  198. //        - arr: vector of integers
  199. //      Returns:
  200. //        - the minimum XOR value between any pair (i != j).
  201. //      Time complexity: O(n * LOG)
  202. //      Constraint: arr must have at least 2 elements.
  203. //      NOTE: An easier method is to sort the array, the minimum XOR pair
  204. //            will be between adjacent elements after sorting. This trie
  205. //            method works too but is slower (though still O(n LOG)).
  206. int minXorPair(vector<int>& arr) {
  207.     BinaryTrie trie;
  208.     trie.insert(arr[0]);
  209.     int ans = INT_MAX;
  210.     for (int i = 1; i < (int)arr.size(); i++) {
  211.         ans = min(ans, trie.minXor(arr[i]));
  212.         trie.insert(arr[i]);
  213.     }
  214.     return ans;
  215. }
  216.  
  217. // 3.3) Count the number of pairs (i < j) such that (arr[i] XOR arr[j]) < K.
  218. //      Parameters:
  219. //        - arr: vector of integers
  220. //        - K: threshold (non-negative)
  221. //      Returns:
  222. //        - total number of unordered pairs with XOR < K.
  223. //      Time complexity: O(n * LOG)
  224. //      Constraint: K >= 0. If K == 0, answer is 0.
  225. long long countPairsXorLessThan(vector<int>& arr, int K) {
  226.     if (K <= 0) return 0;
  227.     BinaryTrie trie;
  228.     long long ans = 0;
  229.     for (int x : arr) {
  230.         ans += trie.countXorLessThan(x, K);
  231.         trie.insert(x);
  232.     }
  233.     return ans;
  234. }
  235.  
  236. // 3.4) Count the number of subarrays whose XOR is < K.
  237. //      We use prefix XOR: pref[i] = XOR of arr[0..i-1].
  238. //      A subarray XOR = pref[r] XOR pref[l-1].
  239. //      So we insert each prefix into a trie and count how many previous
  240. //      prefixes give XOR < K with the current prefix.
  241. //      Parameters:
  242. //        - arr: vector of integers
  243. //        - K: threshold (non-negative)
  244. //      Returns:
  245. //        - number of contiguous subarrays with XOR < K.
  246. //      Time complexity: O(n * LOG)
  247. //      Constraint: K >= 0. If K == 0, answer is 0 because XOR of empty? no.
  248. long long countSubarraysXorLessThan(vector<int>& arr, int K) {
  249.     if (K <= 0) return 0;
  250.     BinaryTrie trie;
  251.     trie.insert(0); // prefix 0 for empty subarray
  252.     long long ans = 0;
  253.     int pref = 0;
  254.     for (int x : arr) {
  255.         pref ^= x;
  256.         ans += trie.countXorLessThan(pref, K);
  257.         trie.insert(pref);
  258.     }
  259.     return ans;
  260. }
  261.  
  262. // 3.5) Maximum XOR of any subarray.
  263. //      Equivalent to maximum difference between two prefix XORs.
  264. //      We insert prefix XORs and query maxXor for each prefix.
  265. //      Parameters:
  266. //        - arr: vector of integers
  267. //      Returns:
  268. //        - the maximum XOR value of any subarray.
  269. //      Time complexity: O(n * LOG)
  270. //      Constraint: arr non-empty.
  271. int maxSubarrayXor(vector<int>& arr) {
  272.     BinaryTrie trie;
  273.     trie.insert(0);
  274.     int pref = 0, ans = 0;
  275.     for (int x : arr) {
  276.         pref ^= x;
  277.         ans = max(ans, trie.maxXor(pref));
  278.         trie.insert(pref);
  279.     }
  280.     return ans;
  281. }
  282.  
  283. // ===================================================================
  284. // SECTION 4: Sliding Window Binary Trie (with insert/delete)
  285. // ===================================================================
  286.  
  287. // This class extends the basic trie with the ability to erase elements
  288. // (already present in BinaryTrie). You can use it in a two-pointer
  289. // / sliding window scenario where you add numbers to the right and
  290. // remove from the left while maintaining the trie.
  291. //
  292. // Example: Count subarrays with XOR <= K in O(n LOG) using two pointers?
  293. // But careful: sliding window with XOR does NOT work with monotonicity
  294. // because XOR is not monotonic. However, if the problem involves AND/OR,
  295. // but for XOR we use prefix + trie. Still, this insert/erase trie can
  296. // be used for other constraints like "maximum XOR of subarray with
  297. // length at most L" etc.
  298.  
  299. // The BinaryTrie class already has erase() and insert().
  300. // So no additional class is needed; just use BinaryTrie and call erase.
  301.  
  302. // ===================================================================
  303. // SECTION 5: Persistent Binary Trie (for range queries)
  304. // ===================================================================
  305.  
  306. // A Persistent Binary Trie allows you to query maximum XOR with x using
  307. // only prefix XORs that lie inside an index range [L, R].
  308. // This is useful when you have an array and many queries asking:
  309. // "Given L, R, and x, find max XOR of x with any element in arr[L..R]".
  310. //
  311. // We build a persistent trie over the array elements (or prefix XORs).
  312. // Each version corresponds to inserting one more element.
  313. // To query range [L, R], we use version R and version L-1 and subtract counts.
  314. //
  315. // NOTE: This is an advanced data structure. Use only when needed.
  316. // The code below is a simplified implementation for integers with LOG bits.
  317.  
  318. struct PersistentNode {
  319.     int child[2];
  320.     int cnt;
  321.     PersistentNode() {
  322.         child[0] = child[1] = -1;
  323.         cnt = 0;
  324.     }
  325. };
  326.  
  327. class PersistentBinaryTrie {
  328. public:
  329.     vector<PersistentNode> tr;
  330.     vector<int> root; // root[i] = node index after inserting first i elements
  331.  
  332.     PersistentBinaryTrie() {
  333.         tr.push_back(PersistentNode()); // node 0 is null/empty
  334.         root.push_back(0);
  335.     }
  336.  
  337.     // Insert value x into the trie and return the new root node index.
  338.     // This creates a new version without modifying previous nodes.
  339.     int insert(int prevRoot, int x) {
  340.         int newRoot = tr.size();
  341.         tr.push_back(tr[prevRoot]);
  342.         tr[newRoot].cnt++;
  343.         int curNew = newRoot;
  344.         int curPrev = prevRoot;
  345.         for (int bit = LOG; bit >= 0; bit--) {
  346.             int b = (x >> bit) & 1;
  347.             // copy the previous node's child pointers
  348.             int prevChild = (curPrev == -1) ? -1 : tr[curPrev].child[b];
  349.             int newChild = tr.size();
  350.             tr.push_back(PersistentNode());
  351.             if (prevChild != -1) {
  352.                 tr[newChild] = tr[prevChild];
  353.             }
  354.             tr[newChild].cnt++;
  355.             tr[curNew].child[b] = newChild;
  356.             curNew = newChild;
  357.             curPrev = prevChild;
  358.         }
  359.         return newRoot;
  360.     }
  361.  
  362.     // Build persistent trie from an array of values.
  363.     // The values can be prefix XORs or elements.
  364.     void build(const vector<int>& vals) {
  365.         for (int v : vals) {
  366.             int newRoot = insert(root.back(), v);
  367.             root.push_back(newRoot);
  368.         }
  369.     }
  370.  
  371.     // Query maximum XOR with x using only values inserted in versions
  372.     // (lRoot .. rRoot] i.e. indices [l, r) in the original array.
  373.     // Here lRoot = root[l], rRoot = root[r] (root is 1-indexed in build).
  374.     // If you use build on prefix array pref[0..n], then query(l, r, x)
  375.     // where l and r are prefix indices (l < r) uses pref[l..r-1].
  376.     int queryRangeMaxXor(int lRoot, int rRoot, int x) {
  377.         int ans = 0;
  378.         int nodeL = lRoot, nodeR = rRoot;
  379.         for (int bit = LOG; bit >= 0; bit--) {
  380.             int b = (x >> bit) & 1;
  381.             int want = b ^ 1;
  382.             int cntWant = 0;
  383.             if (tr[nodeR].child[want] != -1) {
  384.                 cntWant = tr[tr[nodeR].child[want]].cnt;
  385.             }
  386.             if (tr[nodeL].child[want] != -1) {
  387.                 cntWant -= tr[tr[nodeL].child[want]].cnt;
  388.             }
  389.             if (cntWant > 0) {
  390.                 ans |= (1 << bit);
  391.                 nodeR = tr[nodeR].child[want];
  392.                 nodeL = tr[nodeL].child[want];
  393.             } else {
  394.                 nodeR = tr[nodeR].child[b];
  395.                 nodeL = tr[nodeL].child[b];
  396.             }
  397.         }
  398.         return ans;
  399.     }
  400. };
  401.  
  402. // Example of using Persistent Trie for range maximum XOR queries.
  403. // Suppose you have an array arr and you need to answer q queries:
  404. // For each query (l, r, x) 1-indexed inclusive, find max XOR of x
  405. // with any arr[i] where l <= i <= r.
  406. // You can build persistent trie on arr (1-indexed) and call queryRangeMaxXor(root[l-1], root[r], x).
  407.  
  408. // ===================================================================
  409. // SECTION 6: Common Tricks and Notes from ECPC/ACPC
  410. // ===================================================================
  411.  
  412. // Trick 1: Maximum XOR of two numbers can also be solved by sorting?
  413. //          No, Trie is the standard.
  414.  
  415. // Trick 2: Counting subarrays with XOR in [L, R] can be done by
  416. //          countSubarraysXorLessThan(R+1) - countSubarraysXorLessThan(L)
  417. //          using the same trie function (be careful with L=0).
  418. //          So you can implement:
  419. long long countSubarraysXorInRange(vector<int>& arr, int L, int R) {
  420.     if (L > R) return 0;
  421.     if (L == 0) {
  422.         return countSubarraysXorLessThan(arr, R+1);
  423.     }
  424.     return countSubarraysXorLessThan(arr, R+1) - countSubarraysXorLessThan(arr, L);
  425. }
  426.  
  427. // Trick 3: If you need to count pairs (i, j) with XOR >= K, use total pairs - countPairsXorLessThan(arr, K).
  428. //          total pairs = n*(n-1)/2.
  429. long long countPairsXorGreaterEqual(vector<int>& arr, int K) {
  430.     long long n = arr.size();
  431.     long long total = n * (n - 1) / 2;
  432.     return total - countPairsXorLessThan(arr, K);
  433. }
  434.  
  435. // ===================================================================
  436. // Additional functions for Binary Trie tricks and utilities
  437. // ===================================================================
  438.  
  439. // ===================================================================
  440. // Trick 4 (alternative): Minimum XOR pair using sorting (simpler, O(n log n))
  441. // ===================================================================
  442.  
  443. // 4.1) Minimum XOR of any two numbers in the array using sorting.
  444. //      Parameters:
  445. //        - arr: vector of integers
  446. //      Returns:
  447. //        - the minimum XOR value between any pair (i != j).
  448. //      Time complexity: O(n log n)
  449. //      Constraint: arr must have at least 2 elements.
  450. //      Note: This is simpler than the trie approach and works for static arrays.
  451. //            Sorting adjacent elements works because the minimum XOR pair
  452. //            will always be adjacent after sorting (proof: for any three
  453. //            numbers a < b < c, min(a^b, b^c) <= a^c).
  454. int minXorPairUsingSorting(vector<int>& arr) {
  455.     sort(arr.begin(), arr.end());
  456.     int ans = INT_MAX;
  457.     for (int i = 1; i < (int)arr.size(); i++) {
  458.         ans = min(ans, arr[i] ^ arr[i-1]);
  459.     }
  460.     return ans;
  461. }
  462.  
  463. // ===================================================================
  464. // Trick 7: Maximum XOR between any element from array A and any element from array B
  465. // ===================================================================
  466.  
  467. // 7.1) Given two arrays A and B, find the maximum value of (a XOR b)
  468. //      where a ∈ A and b ∈ B.
  469. //      Parameters:
  470. //        - A, B: vectors of integers
  471. //      Returns:
  472. //        - the maximum XOR value between any a in A and b in B.
  473. //      Time complexity: O((n+m) * LOG) where n = A.size(), m = B.size()
  474. //      Constraint: both arrays non-empty.
  475. //      Note: We insert all elements of A into a trie, then for each b in B
  476. //            query the maximum XOR.
  477. int maxXorFromTwoArrays(const vector<int>& A, const vector<int>& B) {
  478.     BinaryTrie trie;
  479.     for (int a : A) trie.insert(a);
  480.     int ans = 0;
  481.     for (int b : B) {
  482.         ans = max(ans, trie.maxXor(b));
  483.     }
  484.     return ans;
  485. }
  486.  
  487. // ===================================================================
  488. // Trick 5: "MUBIS" – common ECPC problems: Maximum XOR Subarray or Minimum XOR Pair
  489. //          The functions maxSubarrayXor and minXorPair (and maxXorPair)
  490. //          are already provided in the main template. They cover these.
  491. // ===================================================================
  492.  
  493. // ===================================================================
  494. // Trick 6: Using erase() for sliding window / dynamic sets
  495. //          The BinaryTrie class already supports erase() by decreasing cnt.
  496. //          Below is an example of how to use it to count pairs (i, j)
  497. //          within a window [L, R] that satisfy (arr[i] XOR arr[j]) < K.
  498. //          However, since XOR is not monotonic, a sliding window is not
  499. //          usually used for counting subarrays with XOR < K (prefix trie is better).
  500. //          But this example demonstrates the use of insert/erase for dynamic
  501. //          sets in general, which can be applied to other bitwise operations
  502. //          (like AND/OR) where monotonicity holds.
  503. // ===================================================================
  504.  
  505. // This function is just an example; it counts the number of pairs (i, j)
  506. // with L <= i < j <= R such that (arr[i] XOR arr[j]) < K.
  507. // It uses a trie that is updated as the window slides.
  508. // Parameters:
  509. //   - arr: the array
  510. //   - L, R: inclusive indices of the window
  511. //   - K: threshold
  512. // Returns:
  513. //   - number of pairs in that window with XOR < K.
  514. // Time complexity: O((R-L+1) * LOG)
  515. long long countPairsXorLessThanInWindow(const vector<int>& arr, int L, int R, int K) {
  516.     if (K <= 0 || L >= R) return 0;
  517.     BinaryTrie trie;
  518.     long long ans = 0;
  519.     // Insert elements from L to R one by one and count pairs
  520.     for (int i = L; i <= R; i++) {
  521.         ans += trie.countXorLessThan(arr[i], K);
  522.         trie.insert(arr[i]);
  523.     }
  524.     return ans;
  525. }
  526.  
  527. // Example of sliding window with insert/erase (maintaining a window of fixed size):
  528. // Suppose we want to answer many queries (L, R) quickly, we can precompute?
  529. // Not needed here; the above function just shows usage.
  530.  
  531. // ===================================================================
  532. // Utility: Build a trie from a vector (convenience function)
  533. // ===================================================================
  534.  
  535. // This function builds a BinaryTrie from a vector of integers.
  536. // Parameters:
  537. //   - vals: vector of integers
  538. // Returns:
  539. //   - a BinaryTrie object containing all values.
  540. BinaryTrie buildTrieFromVector(const vector<int>& vals) {
  541.     BinaryTrie trie;
  542.     for (int x : vals) trie.insert(x);
  543.     return trie;
  544. }
  545.  
  546. // ===================================================================
  547. // Additional: Count of numbers in trie that are <= x (not directly XOR)
  548. // Not common, but useful for some bitwise problems.
  549. // The BinaryTrie can be extended to count numbers less than x.
  550. // ===================================================================
  551.  
  552. // This function counts how many numbers stored in the trie are strictly less than x.
  553. // Parameters:
  554. //   - x: threshold
  555. // Returns:
  556. //   - count of stored numbers y such that y < x.
  557. // Time complexity: O(LOG)
  558. // Note: This works because we store bits from MSB to LSB, and we can traverse
  559. //       to count numbers less than x.
  560. //       This is not a typical XOR query but can be used in combination.
  561. int countLessThanInTrie(BinaryTrie& trie, int x) {
  562.     int node = 0;
  563.     int ans = 0;
  564.     for (int bit = LOG; bit >= 0; bit--) {
  565.         if (node == -1 || trie.tr[node].cnt == 0) break;
  566.         int xb = (x >> bit) & 1;
  567.         if (xb == 1) {
  568.             // add count of numbers with bit 0 at this position (they are smaller)
  569.             int zeroChild = trie.tr[node].child[0];
  570.             if (zeroChild != -1) ans += trie.tr[zeroChild].cnt;
  571.             // then continue with bit 1 to match x
  572.             node = trie.tr[node].child[1];
  573.         } else {
  574.             // xb == 0, we must continue with bit 0 to stay less or equal
  575.             node = trie.tr[node].child[0];
  576.         }
  577.     }
  578.     // At the end, if we followed exactly x, we didn't count it (strictly less)
  579.     return ans;
  580. }
  581.  
  582. // ===================================================================
  583. // Another utility: Count numbers in trie with XOR in range [L, R]
  584. // ===================================================================
  585.  
  586. // Count how many stored numbers y satisfy L <= (x XOR y) <= R.
  587. // This can be done using countXorLessThan twice.
  588. int countXorInRange(BinaryTrie& trie, int x, int L, int R) {
  589.     if (L > R) return 0;
  590.     int right = trie.countXorLessThan(x, R+1);
  591.     int left = trie.countXorLessThan(x, L);
  592.     return right - left;
  593. }
  594.  
  595. // ===================================================================
  596. // New section: Advanced - Maximum XOR of subarray with length at most K
  597. // ===================================================================
  598.  
  599. // Problem: Given an array arr, find the maximum XOR of any subarray
  600. // whose length is at most K (or exactly K, etc.)
  601. // Using prefix XOR and a trie that supports deletion to maintain only
  602. // prefixes that are within the last K positions.
  603. // Parameters:
  604. //   - arr: vector of integers
  605. //   - K: maximum length of subarray (K >= 1)
  606. // Returns:
  607. //   - maximum XOR of any subarray of length <= K.
  608. // Time complexity: O(n * LOG)
  609. // Constraint: K >= 1.
  610. int maxSubarrayXorAtMostK(const vector<int>& arr, int K) {
  611.     int n = arr.size();
  612.     if (n == 0) return 0;
  613.     BinaryTrie trie;
  614.     trie.insert(0); // prefix 0
  615.     int pref = 0;
  616.     int ans = 0;
  617.     // We'll keep a queue of prefix values to remove those that fall out of the window.
  618.     queue<int> prefixes; // store prefix values in order
  619.     prefixes.push(0);
  620.  
  621.     for (int i = 0; i < n; i++) {
  622.         pref ^= arr[i];
  623.         // insert current prefix
  624.         trie.insert(pref);
  625.         prefixes.push(pref);
  626.  
  627.         // If window size exceeds K, remove the oldest prefix
  628.         if ((int)prefixes.size() > K + 1) { // because we have prefix for each position
  629.             int old = prefixes.front();
  630.             prefixes.pop();
  631.             trie.erase(old);
  632.         }
  633.  
  634.         // Query max XOR with current prefix
  635.         ans = max(ans, trie.maxXor(pref));
  636.     }
  637.     return ans;
  638. }
  639.  
  640. // ===================================================================
  641. // End of additions
  642. // ===================================================================
  643.  
  644. // ===================================================================
  645. // SECTION 7: Utility function: build from vector and standard queries
  646. // ===================================================================
  647.  
  648. // The BinaryTrie class is dynamic and you can insert any number of elements.
  649. // The PersistentBinaryTrie is for static arrays with many range queries.
  650.  
  651. // ===================================================================
  652. // main() – Example usage (can be ignored)
  653. // ===================================================================
  654.  
  655. int main() {
  656.     ios::sync_with_stdio(false);
  657.     cin.tie(nullptr);
  658.  
  659.     // Example 1: max XOR pair
  660.     vector<int> arr = {3, 10, 5, 25, 2, 8};
  661.     cout << "Max XOR pair = " << maxXorPair(arr) << "\n"; // 28 (5^25)
  662.  
  663.     // Example 2: count subarrays with XOR < 10
  664.     vector<int> nums = {1, 2, 3, 4};
  665.     cout << "Subarrays XOR < 10: " << countSubarraysXorLessThan(nums, 10) << "\n";
  666.  
  667.     // Example 3: Persistent trie range query
  668.     vector<int> vals = {1, 2, 3, 4};
  669.     PersistentBinaryTrie pTrie;
  670.     pTrie.build(vals); // builds versions for prefix elements
  671.     // query max XOR with x=5 among values in range [1,3] (1-indexed)
  672.     int l = 1, r = 3, x = 5;
  673.     int ans = pTrie.queryRangeMaxXor(pTrie.root[l-1], pTrie.root[r], x);
  674.     cout << "Max XOR in range [1,3] with 5 = " << ans << "\n";
  675.  
  676.     return 0;
  677. }
Success #stdin #stdout 0s 5328KB
comments (?)
stdin 
Standard input is empty
stdout 
Max XOR pair = 28
Subarrays XOR < 10: 10
Max XOR in range [1,3] with 5 = 7
https://ideone.com/1CnN93
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!