daily pastebin goal
65%
SHARE
TWEET

Lexicographicaly Longest Increasing Subsequence

keverman Mar 13th, 2018 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct node
  2. {
  3.     int val, parent;
  4.  
  5.     node() {}
  6.    
  7.     node(int val, int parent)
  8.     {
  9.         this -> val = val;
  10.         this -> parent = parent;
  11.     }
  12. };
  13.  
  14. int pos(std::vector<std::vector<node> > &tail, unsigned int lhs, unsigned int rhs, int key)
  15. {
  16.     while(rhs - 1 > lhs)
  17.     {
  18.         int mid = lhs + (rhs - lhs) / 2;
  19.         tail[mid].back().val >= key ? rhs = mid : lhs = mid;
  20.     }
  21.  
  22.     if(rhs == tail.size() - 1)
  23.     {
  24.         tail.push_back(std::vector<node>(1, node(INF, 0)));
  25.         tail[tail.size() - 2].resize(0);
  26.     }
  27.  
  28.     return rhs;
  29. }
  30.  
  31. std::vector<int> LexMinLIS(std::vector<int> &seq)
  32. {
  33.     std::vector<int> LexMin;
  34.     std::vector<std::vector<node> > tail(3);
  35.     tail[0].push_back(node(-INF, -1)), tail[1].push_back(node(seq[0], 0)), tail[2].push_back(node(INF, 0));
  36.  
  37.     for(unsigned int i = 1; i < seq.size(); i++)
  38.     {
  39.         int p = pos(tail, 0, tail.size(), seq[i]);
  40.         tail[p].push_back(node(seq[i], tail[p - 1].size() - 1));
  41.     }
  42.    
  43.     node c = tail[tail.size() - 2].back();
  44.    
  45.     for(unsigned int i = tail.size() - 2; i > 0; i--)
  46.     {
  47.         LexMin.push_back(c.val);
  48.         c = tail[i - 1][c.parent];
  49.     }
  50.    
  51.     return LexMin;
  52. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top