| 1 | vi lis(vi arr) { |
| 2 | if (arr.empty()) return vi(); |
| 3 | vi seq, back(size(arr)), ans; |
| 4 | rep(i,0,size(arr)) { |
| 5 | int res = 0, lo = 1, hi = size(seq); |
| 6 | while (lo <= hi) { |
| 7 | int mid = (lo+hi)/2; |
| 8 | if (arr[seq[mid-1]] < arr[i]) res = mid, lo = mid + 1; |
| 9 | else hi = mid - 1; } |
| 10 | if (res < size(seq)) seq[res] = i; |
| 11 | else seq.push_back(i); |
| 12 | back[i] = res == 0 ? -1 : seq[res-1]; } |
| 13 | int at = seq.back(); |
| 14 | while (at != -1) ans.push_back(at), at = back[at]; |
| 15 | reverse(ans.begin(), ans.end()); |
| 16 | return ans; } |
| 17 | // vim: cc=60 ts=2 sts=2 sw=2: |