alan23273850 的刷題筆記
d242: 00481 - What Goes Up
出處：https://zerojudge.tw/ShowProblem?problemid=d242
提交：https://zerojudge.tw/Submissions?problemid=d242&account=allllllan123456
問題：給你大約 500000 個整數，請求出最晚出現的最長 (嚴格) 遞增子序列 (longest increasing subsequence, LIS)。
解法：因為這題資料量較大，我們必須在 $\mathcal O(n\log_2n)$ 時間內完成，詳細作法可參考本站介紹最長遞增子序列的頁面。
1#include <bits/stdc++.h>
2using namespace std;
3
4// Ref: http://www.csie.ntnu.edu.tw/~u91029/LongestIncreasingSubsequence.html#3
5
6int n, dpLen, stackLen;
7int arr[500000], dp[500000], len[500000], stacK[500000];
8
9int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
10 while (cin >> arr[n]) {
11 int lb = 1, ub = dpLen, index = ub+1;
12 while (lb <= ub) {
13 int mid = (lb + ub) / 2;
14 if (dp[mid] >= arr[n]) ub = mid - 1, index = mid;
15 else lb = mid + 1;
16 }
17 len[n] = index;
18 dp[index] = arr[n++];
19 if (index > dpLen) dpLen = index;
20 }
21 cout << dpLen << "\n-\n";
22 for (n--; n>=0 && dpLen; n--)
23 if (len[n] == dpLen)
24 stacK[stackLen++] = arr[n],
25 dpLen--;
26 while (stackLen)
27 cout << stacK[--stackLen] << '\n';
28 return 0;
29}