fork(2) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <algorithm>
  5. #include <utility>
  6.  
  7. using namespace std;
  8.  
  9.     void update(int rank, int increment, vector<int>& binaryIndexTree)
  10. 	{
  11. 	    while (rank < binaryIndexTree.size()) { // Increment the current rank and all higher ranks
  12. 	        binaryIndexTree[rank - 1] += increment;
  13. 	        rank += (rank & -rank);
  14. 	    }
  15. 	}
  16.  
  17. 	int getValue(int rank, const vector<int>& binaryIndexTree)
  18. 	{
  19. 	    auto result = 0;
  20. 	    while (rank > 0) { // Search the current rank and all lower ranks
  21. 	        result += binaryIndexTree[rank - 1]; // Sum any value found into result
  22.             rank -= (rank & -rank);
  23. 	    }
  24. 	    return result;
  25. 	}
  26.  
  27. int main(void) {
  28.    vector<int> values{ 2, 3, 4, 3, 4, 1 };
  29.  
  30.    // O(n*n) solution
  31.    vector<int> largerNumbers(values.size());
  32.    auto count = 0;
  33.  
  34.     for (int i = values.size() - 1; i >= 0; --i){
  35.         for (int j = i + 1; j < values.size(); ++j){
  36.             if (values[i] < values[j]){
  37.                 largerNumbers[i]++;
  38.                 count += largerNumbers[j];
  39.             }
  40.         }
  41.     }
  42.     cout << "O(n*n): " << count << endl;
  43.  
  44.     // O(nklogn) solution
  45.     int n = values.size(), k = 3; // k is the length of the subsequesnces
  46.     vector<vector<int>> cumBIT(k, vector<int>(n)); // 0 out cumBIT this is the binary tree
  47.     vector<int> temp(n); // Array for sorting
  48.     map<int, int> mapIndex; // This will translate from the value in index to the 1-based count of values less than it
  49.  
  50.     partial_sort_copy(values.cbegin(), values.cend(), temp.begin(), temp.end());
  51.  
  52.     for(auto i = 0; i < n; ++i){
  53.         mapIndex.insert(make_pair(temp[i], i + 1)); // insert will only allow each number to be added to the map the first time
  54.     }
  55.  
  56.     vector<vector<int>> binaryIndexTree(k, vector<int>(n)); // A 2D binary index tree with depth k
  57.     auto result = 0;
  58.  
  59.     for(auto it = values.cbegin(); it != values.cend(); ++it){
  60.         auto rank = mapIndex[*it];
  61.         auto value = 1; // Number of sequences to be added to this rank and all subsequent ranks
  62.         update(rank, value, binaryIndexTree[0]); // Populate the binary index tree for sub-sequences of length 1
  63.  
  64.         for(auto i = 1; i < k; ++i){ // Itterate over all sub-sequence lengths 2 - k
  65.             value = getValue(rank - 1, binaryIndexTree[i - 1]); // Retrieve all possible shorter sub-sequences of lesser or equal rank
  66.             update(rank, value, binaryIndexTree[i]); // Update the binary index tree for sub sequences of this length
  67.         }
  68.         result += value; // Add the possible sub-sequences of length k for this rank
  69.     }
  70.  
  71.     cout << "O(nklogn): " << result << endl;
  72.     return 0;
  73. }
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
O(n*n): 3
O(nklogn): 3
https://ideone.com/GdF0me
language:
C++14 (gcc 8.3)
created:
9 years 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!