最长上升子序列【nlogn+路径输出】

#include <iostream>
#include <algorithm>
#include <functional>
#include <string.h>
using namespace std;typedef long long ll;const int maxn = 1e5 + 7;
int dp[maxn];
int pos[maxn];	// 记录每个数在dp数组里出现的位置。唯一
int ans[maxn];
int arr[maxn];
int main() {
    memset(dp, 0, sizeof(dp));int n;cin >> n;for (int i = 0; i < n; ++i) {
    cin >> arr[i];}dp[1] = arr[0];int len = 1;for (int i = 1; i < n; ++i) {
    if (arr[i] > dp[len]) {
    dp[++len] = arr[i];pos[i] = len;}else {
    int p = lower_bound(dp + 1, dp + 1 + len, arr[i]) - dp;dp[p] = arr[i];pos[i] = p;}}int t = len;for (int i = n - 1; i >= 0; --i) {
    if (!len)break;if (pos[i] == len) {
    ans[len] = i;--len;}}/*cout << "dp:\t";for (int i = 1; i <= n; ++i) {cout << dp[i] << " ";}cout << endl;cout << "pos:\t";for (int i = 0; i < n; ++i) {cout << pos[i] << " ";}cout << endl;*/for (int i = 1; i <= t; ++i) {
    cout << arr[ans[i]] << " ";}return 0;
}