Truy vết dãy con tăng dài nhất
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho dãy $N$ số nguyên $A_1, A_2, \dots, A_N$. Hãy tìm độ dài $L$ của dãy con tăng nghiêm ngặt dài nhất (LIS) trong thời gian $O(N \log N)$, đồng thời in ra dãy con tăng độ dài $L$ có thứ tự từ điển nhỏ nhất (so sánh theo giá trị các phần tử).
Cấu trúc con tối ưu: tính $lisFrom[i]$ là độ dài LIS bắt đầu tại $i$ (bằng cách tính LDS từ phải sang trái trong $O(N \log N)$), sau đó duyệt từ trái sang phải chọn phần tử nhỏ nhất ở mỗi bước.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên $N$. Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$.
Dữ liệu ra
Dòng đầu tiên in ra số nguyên $L$. Dòng thứ hai in ra $L$ số nguyên là dãy con tìm được.
Ví dụ
| Input | Output |
|---|---|
| 6 3 1 4 2 5 3 |
3 1 2 3 |
| 4 4 3 2 1 |
1 1 |
Giới hạn
$1 \le N \le 10^5$, $|A_i| \le 10^9$.
Community Discussion