fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5. QUESTION IN SIMPLE WORDS
  6. ------------------------
  7. For every array element a[i], find the farthest position to the right
  8. where the value is smaller than a[i].
  9.  
  10. This version returns:
  11. answer[i] = j - i   (distance)
  12.  
  13. If you want the actual index j,
  14. change the marked line below.
  15.  
  16. ------------------------------------------------------------
  17. BRUTE FORCE IDEA
  18. ------------------------------------------------------------
  19. For every i:
  20. - check every j > i
  21. - if a[j] < a[i], keep the farthest such j
  22.  
  23. ------------------------------------------------------------
  24. WHY BRUTE FORCE IS TOO SLOW
  25. ------------------------------------------------------------
  26. That takes O(n^2), which is too slow for large arrays.
  27.  
  28. ------------------------------------------------------------
  29. OPTIMIZED IDEA
  30. ------------------------------------------------------------
  31. Process from right to left.
  32.  
  33. Why right to left?
  34. Because when we are at index i,
  35. all indices to the right have already been seen.
  36.  
  37. We use:
  38. - coordinate compression
  39. - Fenwick tree
  40.  
  41. Fenwick tree stores:
  42. for each compressed value, the maximum index seen so far.
  43.  
  44. Then for a[i], we ask:
  45. among all strictly smaller values, what is the largest index?
  46. That gives the rightmost smaller element.
  47. */
  48.  
  49. struct FenwickMax {
  50.     int n;
  51.     vector<int> bit;
  52.  
  53.     FenwickMax(int n = 0) { init(n); }
  54.  
  55.     void init(int n_) {
  56.         n = n_;
  57.         bit.assign(n + 1, -1);
  58.     }
  59.  
  60.     void update(int idx, int val) {
  61.         for (; idx <= n; idx += idx & -idx) {
  62.             bit[idx] = max(bit[idx], val);
  63.         }
  64.     }
  65.  
  66.     int query(int idx) {
  67.         int ans = -1;
  68.         for (; idx > 0; idx -= idx & -idx) {
  69.             ans = max(ans, bit[idx]);
  70.         }
  71.         return ans;
  72.     }
  73. };
  74.  
  75. vector<int> rightmostSmallerDistance(const vector<int>& a) {
  76.     int n = (int)a.size();
  77.  
  78.     // Step 1: coordinate compression
  79.     vector<int> vals = a;
  80.     sort(vals.begin(), vals.end());
  81.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  82.  
  83.     FenwickMax fw((int)vals.size());
  84.     vector<int> ans(n, 0);
  85.  
  86.     // Step 2: process from right to left
  87.     for (int i = n - 1; i >= 0; i--) {
  88.         int id = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;
  89.  
  90.         // Query all strictly smaller values
  91.         int j = fw.query(id - 1);
  92.  
  93.         if (j == -1) ans[i] = 0;
  94.         else ans[i] = j - i;   // change to ans[i] = j; if actual index is needed
  95.  
  96.         // Add current value/index into Fenwick tree
  97.         fw.update(id, i);
  98.     }
  99.  
  100.     return ans;
  101. }
  102.  
  103. int main() {
  104.     vector<int> a = {8, 2, 5, 3};
  105.     auto ans = rightmostSmallerDistance(a);
  106.  
  107.     for (int x : ans) cout << x << ' ';
  108.     cout << '\n';
  109.  
  110.     return 0;
  111. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3 0 1 0
https://ideone.com/jEDS82
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!