fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ===================================================================
  5. // This file contains a collection of Coordinate Compression algorithms.
  6. // Each function is ready to be used as a "black box".
  7. // Read the comments above each one to understand:
  8. //   - What it solves
  9. //   - What input it expects
  10. //   - What it returns
  11. //   - Time complexity
  12. //   - Important constraints / assumptions
  13. // ===================================================================
  14.  
  15. // ===================================================================
  16. // WHAT IS COORDINATE COMPRESSION?
  17. // ===================================================================
  18. // Coordinate compression is a technique that maps large/sparse values
  19. // (like 10^9, 10^12) to small consecutive integers (0, 1, 2, ...).
  20. // This is useful when:
  21. //   - Values are too large to use as array indices
  22. //   - We only care about the relative order of values, not their actual values
  23. //   - We want to use frequency arrays / Fenwick trees / segment trees
  24. //
  25. // Example:
  26. //   Original: [1000, 1, 1000, 500, 1]
  27. //   Compressed: [2, 0, 2, 1, 0]
  28. //   Now values are in range [0, 2] and can be used as array indices.
  29. // ===================================================================
  30.  
  31. // ===================================================================
  32. // 1) Basic Coordinate Compression
  33. //    These are the core functions for mapping values to ranks.
  34. // ===================================================================
  35.  
  36. // 1.1) Compress a vector of values to ranks starting from 0.
  37. //      PURPOSE:
  38. //        - Takes a vector of values (integers) and replaces each value
  39. //          with its rank (0-based) based on sorted order.
  40. //      INPUT:
  41. //        - arr: vector of integers (will be modified in-place)
  42. //      OUTPUT:
  43. //        - The same vector 'arr' is modified to contain ranks.
  44. //        - Does NOT return anything (void).
  45. //      TIME COMPLEXITY:
  46. //        - O(n log n) where n = arr.size() (due to sorting).
  47. //      CONSTRAINTS:
  48. //        - Works for any integers (positive, negative, zero).
  49. //        - If arr is empty, does nothing.
  50. //      NOTES:
  51. //        - Equal values get the SAME rank.
  52. //        - Ranks are 0-based (smallest value → 0).
  53. //        - Example: [10, 20, 10, 30] → [0, 1, 0, 2]
  54. void compressVector(vector<int>& arr) {
  55.     int n = arr.size();
  56.     if (n == 0) return;
  57.  
  58.     vector<int> sorted = arr;
  59.     sort(sorted.begin(), sorted.end());
  60.     sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
  61.  
  62.     for (int i = 0; i < n; i++) {
  63.         arr[i] = lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin();
  64.     }
  65. }
  66.  
  67. // 1.2) Compress a vector but return the compressed version and the mapping.
  68. //      PURPOSE:
  69. //        - Creates a compressed copy of the input vector.
  70. //        - Also returns the mapping from original value → compressed rank.
  71. //      INPUT:
  72. //        - arr: const vector of integers (original values, not modified)
  73. //      OUTPUT:
  74. //        - Returns a pair:
  75. //          - first: vector<int> containing the compressed ranks
  76. //          - second: vector<int> containing the unique values in sorted order
  77. //      TIME COMPLEXITY:
  78. //        - O(n log n)
  79. //      CONSTRAINTS:
  80. //        - Works for any integers.
  81. //      NOTES:
  82. //        - To get the original value from a rank: mapping[rank]
  83. //        - Example: arr = [100, 200, 100, 300]
  84. //          returns: compressed = [0,1,0,2], mapping = [100,200,300]
  85. pair<vector<int>, vector<int>> compressWithMapping(const vector<int>& arr) {
  86.     vector<int> sorted = arr;
  87.     sort(sorted.begin(), sorted.end());
  88.     sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
  89.  
  90.     vector<int> compressed(arr.size());
  91.     for (int i = 0; i < (int)arr.size(); i++) {
  92.         compressed[i] = lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin();
  93.     }
  94.     return {compressed, sorted};
  95. }
  96.  
  97. // 1.3) Get the rank of a single value in a given sorted unique array.
  98. //      PURPOSE:
  99. //        - Given a sorted vector of unique values, find the rank of a value.
  100. //        - This is useful when you already have the mapping from previous compression.
  101. //      INPUT:
  102. //        - mapping: sorted vector of unique values (must be sorted)
  103. //        - value: the value to find the rank of
  104. //      OUTPUT:
  105. //        - Returns the rank (0-based) if the value exists.
  106. //        - Returns -1 if the value is not found.
  107. //      TIME COMPLEXITY:
  108. //        - O(log n) using binary search.
  109. //      CONSTRAINTS:
  110. //        - mapping MUST be sorted.
  111. //        - mapping should contain unique values (no duplicates).
  112. int getRank(const vector<int>& mapping, int value) {
  113.     auto it = lower_bound(mapping.begin(), mapping.end(), value);
  114.     if (it != mapping.end() && *it == value) {
  115.         return it - mapping.begin();
  116.     }
  117.     return -1;
  118. }
  119.  
  120. // ===================================================================
  121. // 2) Coordinate Compression for Arrays Used in Frequency Counting
  122. //    These functions are useful when you need to count frequencies
  123. //    of values that are too large to use as array indices directly.
  124. // ===================================================================
  125.  
  126. // 2.1) Compress and count frequencies in one step.
  127. //      PURPOSE:
  128. //        - Compresses the array values and counts how many times each rank appears.
  129. //      INPUT:
  130. //        - arr: vector of integers (will be modified to compressed ranks)
  131. //      OUTPUT:
  132. //        - Returns a vector<int> where freq[i] = number of times rank i appears.
  133. //        - Also modifies arr to contain compressed ranks.
  134. //      TIME COMPLEXITY:
  135. //        - O(n log n)
  136. //      CONSTRAINTS:
  137. //        - Works for any integers.
  138. //      NOTES:
  139. //        - After calling this function:
  140. //          - arr contains ranks (0, 1, 2, ...)
  141. //          - freq.size() = number of distinct values
  142. //          - The original values are lost (arr is modified).
  143. vector<int> compressAndCount(vector<int>& arr) {
  144.     vector<int> sorted = arr;
  145.     sort(sorted.begin(), sorted.end());
  146.     sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
  147.  
  148.     for (int i = 0; i < (int)arr.size(); i++) {
  149.         arr[i] = lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin();
  150.     }
  151.  
  152.     vector<int> freq(sorted.size(), 0);
  153.     for (int x : arr) {
  154.         freq[x]++;
  155.     }
  156.     return freq;
  157. }
  158.  
  159. // 2.2) Get frequency of values in a range using compressed coordinates.
  160. //      PURPOSE:
  161. //        - Counts how many values in the array fall within [L, R] (inclusive).
  162. //        - Uses coordinate compression to handle large values.
  163. //      INPUT:
  164. //        - arr: vector of integers (original values, not modified)
  165. //        - L, R: the inclusive range [L, R] of values to count
  166. //      OUTPUT:
  167. //        - Returns the count of elements in arr that satisfy L <= value <= R.
  168. //      TIME COMPLEXITY:
  169. //        - O(n log n) for preprocessing + O(log n) per query.
  170. //        - If called multiple times, you can preprocess once and query many times.
  171. //      CONSTRAINTS:
  172. //        - Works for any integers.
  173. //      NOTES:
  174. //        - This function sorts arr internally (makes a copy).
  175. //        - For multiple queries, it's better to use a Fenwick tree or segment tree.
  176. int countInRange(vector<int>& arr, int L, int R) {
  177.     vector<int> sorted = arr;
  178.     sort(sorted.begin(), sorted.end());
  179.     int left = lower_bound(sorted.begin(), sorted.end(), L) - sorted.begin();
  180.     int right = upper_bound(sorted.begin(), sorted.end(), R) - sorted.begin();
  181.     return right - left;
  182. }
  183.  
  184. // ===================================================================
  185. // 3) Coordinate Compression for 2D Points / Grids
  186. //    Useful for problems involving points on a plane.
  187. // ===================================================================
  188.  
  189. // 3.1) Compress both X and Y coordinates of a set of points.
  190. //      PURPOSE:
  191. //        - Takes a list of points (x, y) and compresses both coordinates.
  192. //        - This is useful for grid problems where coordinates are large.
  193. //      INPUT:
  194. //        - points: vector of pairs (x, y) - original coordinates
  195. //      OUTPUT:
  196. //        - Returns a vector of pairs where both x and y are compressed ranks.
  197. //        - Also returns the mapping for x and y coordinates separately.
  198. //      TIME COMPLEXITY:
  199. //        - O(n log n)
  200. //      CONSTRAINTS:
  201. //        - Works for any integers.
  202. //      NOTES:
  203. //        - Points are compressed independently (x and y separate).
  204. //        - Example: [(100,200), (100,300), (500,200)]
  205. //          returns: [(0,0), (0,1), (1,0)]
  206. tuple<vector<pair<int,int>>, vector<int>, vector<int>> compress2DPoints(
  207.     const vector<pair<int,int>>& points
  208. ) {
  209.     vector<int> xs, ys;
  210.     for (auto& p : points) {
  211.         xs.push_back(p.first);
  212.         ys.push_back(p.second);
  213.     }
  214.  
  215.     sort(xs.begin(), xs.end());
  216.     xs.erase(unique(xs.begin(), xs.end()), xs.end());
  217.     sort(ys.begin(), ys.end());
  218.     ys.erase(unique(ys.begin(), ys.end()), ys.end());
  219.  
  220.     vector<pair<int,int>> compressed;
  221.     for (auto& p : points) {
  222.         int cx = lower_bound(xs.begin(), xs.end(), p.first) - xs.begin();
  223.         int cy = lower_bound(ys.begin(), ys.end(), p.second) - ys.begin();
  224.         compressed.push_back({cx, cy});
  225.     }
  226.  
  227.     return {compressed, xs, ys};
  228. }
  229.  
  230. // ===================================================================
  231. // 4) Coordinate Compression for Fenwick Tree / Segment Tree
  232. //    These functions prepare data for range query data structures.
  233. // ===================================================================
  234.  
  235. // 4.1) Prepare a frequency array for Fenwick tree with compressed coordinates.
  236. //      PURPOSE:
  237. //        - Compresses values and creates a frequency array that can be used
  238. //          with a Fenwick tree (Binary Indexed Tree) for prefix sum queries.
  239. //      INPUT:
  240. //        - arr: vector of integers (original values)
  241. //      OUTPUT:
  242. //        - Returns a vector<int> freq where freq[i] = count of value with rank i.
  243. //        - The compressed values can then be used as indices in a Fenwick tree.
  244. //      TIME COMPLEXITY:
  245. //        - O(n log n)
  246. //      CONSTRAINTS:
  247. //        - Works for any integers.
  248. //      NOTES:
  249. //        - This is just a helper; you still need to build the Fenwick tree.
  250. //        - Example: arr = [10, 20, 10, 30, 20]
  251. //          returns: freq = [2, 2, 1] (ranks: 10→0, 20→1, 30→2)
  252. vector<int> prepareFenwickFreq(const vector<int>& arr) {
  253.     vector<int> sorted = arr;
  254.     sort(sorted.begin(), sorted.end());
  255.     sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
  256.  
  257.     vector<int> freq(sorted.size(), 0);
  258.     for (int x : arr) {
  259.         int rank = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
  260.         freq[rank]++;
  261.     }
  262.     return freq;
  263. }
  264.  
  265. // 4.2) Get compressed indices for a Fenwick tree with optional offset.
  266. //      PURPOSE:
  267. //        - Compresses values and optionally shifts them to start from 1.
  268. //        - Fenwick trees typically use 1-based indexing.
  269. //      INPUT:
  270. //        - arr: vector of integers (original values)
  271. //        - oneBased: if true, ranks start from 1 instead of 0
  272. //      OUTPUT:
  273. //        - Returns a vector<int> containing compressed ranks.
  274. //        - If oneBased is true, ranks are 1, 2, 3, ... (not 0, 1, 2, ...)
  275. //      TIME COMPLEXITY:
  276. //        - O(n log n)
  277. //      CONSTRAINTS:
  278. //        - Works for any integers.
  279. //      NOTES:
  280. //        - Use oneBased=true when the compressed values will be used as
  281. //          indices in a Fenwick tree (which is 1-indexed).
  282. vector<int> compressForFenwick(const vector<int>& arr, bool oneBased = true) {
  283.     vector<int> sorted = arr;
  284.     sort(sorted.begin(), sorted.end());
  285.     sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
  286.  
  287.     vector<int> result(arr.size());
  288.     for (int i = 0; i < (int)arr.size(); i++) {
  289.         int rank = lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin();
  290.         result[i] = rank + (oneBased ? 1 : 0);
  291.     }
  292.     return result;
  293. }
  294.  
  295. // ===================================================================
  296. // 5) Advanced Techniques: Using Compression for "Difference Array"
  297. //    on large coordinate ranges (sweep line).
  298. // ===================================================================
  299.  
  300. // 5.1) Sweep line with coordinate compression for range updates.
  301. //      PURPOSE:
  302. //        - Given a list of range updates [L, R] with a value to add,
  303. //          compute the final values at compressed coordinates.
  304. //        - This is useful when coordinates are large and sparse.
  305. //      INPUT:
  306. //        - updates: vector of triples (L, R, val) where:
  307. //          - L: left endpoint (inclusive)
  308. //          - R: right endpoint (inclusive)
  309. //          - val: value to add to all positions in [L, R]
  310. //      OUTPUT:
  311. //        - Returns a vector of pairs (coordinate, accumulated_value)
  312. //          for each unique coordinate that appears in any update.
  313. //      TIME COMPLEXITY:
  314. //        - O(n log n) where n = updates.size()
  315. //      CONSTRAINTS:
  316. //        - Works for any integer coordinates.
  317. //        - L <= R for each update.
  318. //      NOTES:
  319. //        - This is the "difference array" technique on compressed coordinates.
  320. //        - Example: updates = [(1,5,10), (3,7,5)]
  321. //          returns: [(1,10), (3,15), (6,5), (8,0)]
  322. //          (meaning: from 1 to 2:10, from 3 to 5:15, from 6 to 7:5)
  323. vector<pair<int, long long>> sweepLineCompressed(const vector<tuple<int,int,int>>& updates) {
  324.     vector<int> coords;
  325.     for (auto& [L, R, val] : updates) {
  326.         coords.push_back(L);
  327.         coords.push_back(R + 1); // R+1 marks the end of the range
  328.     }
  329.  
  330.     sort(coords.begin(), coords.end());
  331.     coords.erase(unique(coords.begin(), coords.end()), coords.end());
  332.  
  333.     vector<long long> diff(coords.size(), 0);
  334.     for (auto& [L, R, val] : updates) {
  335.         int lIdx = lower_bound(coords.begin(), coords.end(), L) - coords.begin();
  336.         int rIdx = lower_bound(coords.begin(), coords.end(), R + 1) - coords.begin();
  337.         diff[lIdx] += val;
  338.         diff[rIdx] -= val;
  339.     }
  340.  
  341.     vector<pair<int, long long>> result;
  342.     long long cur = 0;
  343.     for (int i = 0; i < (int)coords.size(); i++) {
  344.         cur += diff[i];
  345.         result.push_back({coords[i], cur});
  346.     }
  347.     return result;
  348. }
  349.  
  350. // ===================================================================
  351. // 6) Coordinate Compression for Offline Queries
  352. //    Preprocessing for answering queries on compressed values.
  353. // ===================================================================
  354.  
  355. // 6.1) Offline processing: compress all values from array and queries together.
  356. //      PURPOSE:
  357. //        - In many problems, queries reference values that may not exist in the array.
  358. //        - This function compresses ALL values (from array and queries) together.
  359. //      INPUT:
  360. //        - arr: vector of integers (the main array)
  361. //        - queries: vector of integers (query values to check)
  362. //      OUTPUT:
  363. //        - Returns a pair:
  364. //          - first: vector<int> compressed arr
  365. //          - second: vector<int> compressed queries
  366. //          - Both share the same mapping (all values combined).
  367. //      TIME COMPLEXITY:
  368. //        - O((n+m) log (n+m)) where n=arr.size(), m=queries.size()
  369. //      CONSTRAINTS:
  370. //        - Works for any integers.
  371. //      NOTES:
  372. //        - Useful when you need to answer queries like:
  373. //          "How many elements in arr are <= query_value?"
  374. //        - After compression, you can use a Fenwick tree or sorting.
  375. pair<vector<int>, vector<int>> compressWithQueries(
  376.     const vector<int>& arr, 
  377.     const vector<int>& queries
  378. ) {
  379.     vector<int> allValues = arr;
  380.     for (int x : queries) allValues.push_back(x);
  381.  
  382.     sort(allValues.begin(), allValues.end());
  383.     allValues.erase(unique(allValues.begin(), allValues.end()), allValues.end());
  384.  
  385.     vector<int> compressedArr(arr.size());
  386.     for (int i = 0; i < (int)arr.size(); i++) {
  387.         compressedArr[i] = lower_bound(allValues.begin(), allValues.end(), arr[i]) - allValues.begin();
  388.     }
  389.  
  390.     vector<int> compressedQueries(queries.size());
  391.     for (int i = 0; i < (int)queries.size(); i++) {
  392.         compressedQueries[i] = lower_bound(allValues.begin(), allValues.end(), queries[i]) - allValues.begin();
  393.     }
  394.  
  395.     return {compressedArr, compressedQueries};
  396. }
  397.  
  398. // ===================================================================
  399. // 7) Advanced: Coordinate Compression on Pair/Tuple Values
  400. //    For problems where you need to compress composite keys.
  401. // ===================================================================
  402.  
  403. // 7.1) Compress a vector of pairs (tuple) to ranks.
  404. //      PURPOSE:
  405. //        - Compresses pairs (or tuples) based on lexicographic order.
  406. //        - Useful when you have points (x, y) and need to assign ranks.
  407. //      INPUT:
  408. //        - pairs: vector of pairs (a, b) - values to compress together.
  409. //      OUTPUT:
  410. //        - Returns a vector<int> where each element is the rank of that pair.
  411. //        - Equal pairs get the same rank.
  412. //      TIME COMPLEXITY:
  413. //        - O(n log n)
  414. //      CONSTRAINTS:
  415. //        - Works for any comparable types.
  416. //      NOTES:
  417. //        - Ranks are assigned based on sorted order of pairs.
  418. //        - Example: [(1,2), (2,1), (1,2), (2,2)]
  419. //          returns: [0, 1, 0, 2]
  420. vector<int> compressPairs(const vector<pair<int,int>>& pairs) {
  421.     vector<pair<int,int>> sorted = pairs;
  422.     sort(sorted.begin(), sorted.end());
  423.     sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
  424.  
  425.     vector<int> result(pairs.size());
  426.     for (int i = 0; i < (int)pairs.size(); i++) {
  427.         result[i] = lower_bound(sorted.begin(), sorted.end(), pairs[i]) - sorted.begin();
  428.     }
  429.     return result;
  430. }
  431.  
  432. // ===================================================================
  433. // 8) Tricks & Patterns that appeared in ECPC/ACPC
  434. //    Extra useful techniques involving coordinate compression.
  435. // ===================================================================
  436.  
  437. // 8.1) Compress and find the number of distinct values in each subarray.
  438. //      PURPOSE:
  439. //        - For each subarray [L, R], count how many distinct values appear.
  440. //        - Uses compression to handle large values.
  441. //      INPUT:
  442. //        - arr: vector of integers (original values)
  443. //        - queries: vector of pairs (L, R) - 0-based indices
  444. //      OUTPUT:
  445. //        - Returns a vector<int> where answer[i] = number of distinct values
  446. //          in arr[queries[i].first ... queries[i].second]
  447. //      TIME COMPLEXITY:
  448. //        - O((n+q) log n) using Mo's algorithm with compression.
  449. //      CONSTRAINTS:
  450. //        - Works for any integers.
  451. //        - 0 <= L <= R < n
  452. //      NOTES:
  453. //        - This is a common pattern in ECPC problems.
  454. //        - The function first compresses arr, then uses Mo's algorithm.
  455. //        - Mo's algorithm is a technique for answering range queries offline.
  456. //        - The implementation below is a naive placeholder; for actual Mo's
  457. //          algorithm, replace the inner loop with the standard Mo's approach.
  458. vector<int> distinctInRange(const vector<int>& arr, const vector<pair<int,int>>& queries) {
  459.     // First compress the array
  460.     vector<int> compressed = arr;
  461.     compressVector(compressed);
  462.  
  463.     // Now use Mo's algorithm to answer queries
  464.     // (This is a simplified placeholder - actual Mo's algorithm is more complex)
  465.     int n = compressed.size();
  466.     int q = queries.size();
  467.     vector<int> freq(n, 0);   // size n is safe because ranks are in [0, distinct-1] <= n
  468.     vector<int> answers(q, 0);
  469.  
  470.     // For each query, count distinct values in the range
  471.     // This is O(n*q) for simplicity, but actual Mo's algorithm would be O((n+q)*sqrt(n))
  472.     for (int qi = 0; qi < q; qi++) {
  473.         int L = queries[qi].first;
  474.         int R = queries[qi].second;
  475.  
  476.         fill(freq.begin(), freq.end(), 0);
  477.         int distinct = 0;
  478.         for (int i = L; i <= R; i++) {
  479.             if (freq[compressed[i]] == 0) distinct++;
  480.             freq[compressed[i]]++;
  481.         }
  482.         answers[qi] = distinct;
  483.     }
  484.     return answers;
  485. }
  486.  
  487. // 8.2) Count subarrays with at most K distinct values using compression.
  488. //      PURPOSE:
  489. //        - Counts how many subarrays have at most K distinct values.
  490. //        - Uses compression to handle large values efficiently.
  491. //      INPUT:
  492. //        - arr: vector of integers (original values)
  493. //        - K: maximum number of distinct values allowed
  494. //      OUTPUT:
  495. //        - Returns the total number of subarrays with at most K distinct values.
  496. //      TIME COMPLEXITY:
  497. //        - O(n log n) for compression + O(n) for sliding window.
  498. //      CONSTRAINTS:
  499. //        - Works for any integers.
  500. //        - K >= 0.
  501. //      NOTES:
  502. //        - This is a classic sliding window problem that requires compression.
  503. //        - The sliding window technique: maintain a window [L, R] with <= K distinct.
  504. //        - For each R, extend L as little as possible.
  505. long long countSubarraysAtMostKDistinct(vector<int>& arr, int K) {
  506.     // Compress arr to small ranks
  507.     compressVector(arr);
  508.  
  509.     int n = arr.size();
  510.     long long ans = 0;
  511.     unordered_map<int, int> freq;
  512.     int L = 0;
  513.  
  514.     for (int R = 0; R < n; R++) {
  515.         freq[arr[R]]++;
  516.         while ((int)freq.size() > K) {
  517.             freq[arr[L]]--;
  518.             if (freq[arr[L]] == 0) freq.erase(arr[L]);
  519.             L++;
  520.         }
  521.         ans += (R - L + 1);
  522.     }
  523.     return ans;
  524. }
  525.  
  526. // 8.3) Compress values and find the maximum frequency of any value.
  527. //      PURPOSE:
  528. //        - Finds the value that appears most frequently in the array.
  529. //        - Uses compression to count frequencies efficiently.
  530. //      INPUT:
  531. //        - arr: vector of integers (original values, not modified)
  532. //      OUTPUT:
  533. //        - Returns a pair (value, frequency) where:
  534. //          - value: the original value that appears most often
  535. //          - frequency: how many times it appears
  536. //        - If multiple values have the same max frequency, returns the smallest value.
  537. //      TIME COMPLEXITY:
  538. //        - O(n log n)
  539. //      CONSTRAINTS:
  540. //        - Works for any integers.
  541. //        - arr must not be empty.
  542. pair<int,int> maxFrequencyValue(const vector<int>& arr) {
  543.     auto [compressed, mapping] = compressWithMapping(arr);
  544.     vector<int> freq(mapping.size(), 0);
  545.     for (int x : compressed) freq[x]++;
  546.  
  547.     int maxFreq = 0;
  548.     int maxRank = 0;
  549.     for (int i = 0; i < (int)freq.size(); i++) {
  550.         if (freq[i] > maxFreq) {
  551.             maxFreq = freq[i];
  552.             maxRank = i;
  553.         }
  554.     }
  555.     return {mapping[maxRank], maxFreq};
  556. }
  557.  
  558. // ===================================================================
  559. // 9) Advanced: Coordinate Compression with Coordinate "Shifting"
  560. //    For problems where you need to maintain gaps between coordinates.
  561. // ===================================================================
  562.  
  563. // 9.1) Compress coordinates while preserving gaps (for coordinate compression
  564. //      with distance calculations).
  565. //      PURPOSE:
  566. //        - Sometimes you need to preserve the actual differences between
  567. //          coordinates, not just their order.
  568. //        - This function compresses values but keeps the gaps.
  569. //      INPUT:
  570. //        - coords: vector of integers (sorted or unsorted)
  571. //      OUTPUT:
  572. //        - Returns a vector of integers where each value is mapped to
  573. //          its rank, but preserving gaps.
  574. //      TIME COMPLEXITY:
  575. //        - O(n log n)
  576. //      CONSTRAINTS:
  577. //        - Works for any integers.
  578. //      NOTES:
  579. //        - Example: coords = [1, 3, 10, 100]
  580. //          returns: [0, 1, 2, 3] (no gaps preserved)
  581. //          This is the same as regular compression.
  582. //        - To preserve gaps, you need a different approach (not shown here).
  583. //        - In most cases, regular compression is sufficient.
  584. vector<int> compressPreserveGaps(vector<int>& coords) {
  585.     // This is the same as regular compression for now.
  586.     // Preserving gaps requires more complex mapping that tracks original differences.
  587.     compressVector(coords);
  588.     return coords;
  589. }
  590.  
  591. // ===================================================================
  592. // 10) Helper: Binary Search on Compressed Values
  593. //     Common patterns for querying compressed data.
  594. // ===================================================================
  595.  
  596. // 10.1) Find how many compressed values are < X.
  597. //       PURPOSE:
  598. //         - Counts how many elements in the array are strictly less than X.
  599. //         - Uses compression for efficiency.
  600. //       INPUT:
  601. //         - arr: vector of integers (original values)
  602. //         - X: the threshold value
  603. //       OUTPUT:
  604. //         - Returns the count of elements < X.
  605. //       TIME COMPLEXITY:
  606. //         - O(n log n) for preprocessing + O(log n) per query.
  607. //         - If called once, O(n log n).
  608. //       CONSTRAINTS:
  609. //         - Works for any integers.
  610. int countLessThan(vector<int>& arr, int X) {
  611.     vector<int> sorted = arr;
  612.     sort(sorted.begin(), sorted.end());
  613.     return lower_bound(sorted.begin(), sorted.end(), X) - sorted.begin();
  614. }
  615.  
  616. // 10.2) Find how many compressed values are in [L, R] (inclusive).
  617. //       PURPOSE:
  618. //         - Counts how many elements in the array are in the range [L, R].
  619. //         - Uses compression for efficiency.
  620. //       INPUT:
  621. //         - arr: vector of integers (original values)
  622. //         - L, R: inclusive range
  623. //       OUTPUT:
  624. //         - Returns the count of elements in [L, R].
  625. //       TIME COMPLEXITY:
  626. //         - O(n log n) for preprocessing + O(log n) per query.
  627. int countInRangeSimple(vector<int>& arr, int L, int R) {
  628.     if (L > R) return 0;
  629.     vector<int> sorted = arr;
  630.     sort(sorted.begin(), sorted.end());
  631.     int left = lower_bound(sorted.begin(), sorted.end(), L) - sorted.begin();
  632.     int right = upper_bound(sorted.begin(), sorted.end(), R) - sorted.begin();
  633.     return right - left;
  634. }
  635.  
  636. // ===================================================================
  637. // 11) Common Pitfalls & Tips (Documentation only)
  638. // ===================================================================
  639.  
  640. // ===================================================================
  641. // PITFALL 1: Losing original values after compression.
  642. // SOLUTION: Keep a copy of the original array, or use compressWithMapping.
  643. //
  644. // PITFALL 2: Using compression on negative numbers without care.
  645. // SOLUTION: The functions work with negative numbers just fine.
  646. //           Sorting handles negative values correctly.
  647. //
  648. // PITFALL 3: Not handling duplicate values correctly.
  649. // SOLUTION: Always use 'unique()' to remove duplicates before assigning ranks.
  650. //
  651. // PITFALL 4: Using compressed values as indices without checking bounds.
  652. // SOLUTION: Compressed values are always in range [0, distinct_count - 1].
  653. //           This is safe to use as array indices.
  654. //
  655. // PITFALL 5: Forgetting that compression changes the array.
  656. // SOLUTION: If you need the original values, make a copy before compressing.
  657. // ===================================================================
  658.  
  659. // ===================================================================
  660. // main() with example usage (you can ignore this part)
  661. // ===================================================================
  662.  
  663. int main() {
  664.     ios::sync_with_stdio(false);
  665.     cin.tie(nullptr);
  666.  
  667.     // Example 1: Basic compression
  668.     vector<int> arr = {100, 200, 100, 300, 200, 100};
  669.     cout << "Original: ";
  670.     for (int x : arr) cout << x << " ";
  671.     cout << "\n";
  672.  
  673.     compressVector(arr);
  674.     cout << "Compressed: ";
  675.     for (int x : arr) cout << x << " ";
  676.     cout << "\n"; // Output: 0 1 0 2 1 0
  677.  
  678.     // Example 2: Compression with mapping
  679.     vector<int> arr2 = {10, 20, 10, 30, 20};
  680.     auto [compressed, mapping] = compressWithMapping(arr2);
  681.     cout << "Compressed: ";
  682.     for (int x : compressed) cout << x << " ";
  683.     cout << "\n";
  684.     cout << "Mapping: ";
  685.     for (int x : mapping) cout << x << " ";
  686.     cout << "\n";
  687.  
  688.     // Example 3: Range counting
  689.     vector<int> arr3 = {5, 2, 8, 1, 9, 3, 7};
  690.     cout << "Count in [3, 7]: " << countInRangeSimple(arr3, 3, 7) << "\n"; // 4
  691.  
  692.     // Example 4: Count subarrays with at most 2 distinct
  693.     vector<int> arr4 = {1, 2, 1, 2, 3};
  694.     cout << "Subarrays with at most 2 distinct: " 
  695.          << countSubarraysAtMostKDistinct(arr4, 2) << "\n"; // 12
  696.  
  697.     return 0;
  698. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Original: 100 200 100 300 200 100 
Compressed: 0 1 0 2 1 0 
Compressed: 0 1 0 2 1 
Mapping: 10 20 30 
Count in [3, 7]: 3
Subarrays with at most 2 distinct: 12
https://ideone.com/grDGUv
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!