Computes RSK tableau in O(N sqrt(N) log(N)) time

gistfile1.cpp

vector<vector<int> > bounded_rsk(const vector<int>& A, int k) {
  vector<vector<int> > h(k);
  for(int i = 0; i < A.size(); i++) {
    int x = A[i];
    for(int j = 0; j < k; j++) {
      int p = lower_bound(h[j].begin(), h[j].end(), x) - h[j].begin();
      if(p == h[j].size()) {
        h[j].push_back(x);
        break;
      } else {
        swap(x, h[j][p]);
      }
    }
  }
  return h;
}

vector<vector<int> > fast_rsk(vector<int> A) {
  int rtn = (int)ceil(sqrt(A.size()));
  vector<vector<int> > h_a = bounded_rsk(A, rtn);
  reverse(A.begin(), A.end());
  vector<vector<int> > h_b = bounded_rsk(A, rtn);

  h_a.resize(h_b[0].size());
  for(int i = rtn; i < h_b[0].size(); i++) {
    for(int j = 0; i < h_b[j].size(); j++) {
      h_a[i].push_back(h_b[j][i]);
    }
  }
  return h_a;
}