Truy vết dãy con tăng dài nhất

Binary-search Buổi 22 — DP 2D & LIS Dynamic Programming
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$.

Draft saved