LIS_chặt nhị phân

Bonus: Bài toán LIS sử dụng chặt 
nhị phân 

Bài toán : Cho một dãy số nguyên gồm N phần tử A[1], A[2], ... A[N]. 
Biết rằng dãy con tăng đơn điệu là 1 dãy A[i1],... A[ik] thỏa mãn 
i1 < i2 < ... < ik và A[i1] < A[i2] < .. < A[ik]. Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử? 
Input

• Dòng 1 gồm 1 số nguyên là số N (1 ≤ N ≤ 30000).
• Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 10000).

Output

Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Ban đầu , khi đọc ta sẽ liên tưởng ngay đến bài toán LIS thông thường , Nhưng giờ đây giới hạn của N đã tăng lên rõ rệt , do đó phương án O(n^2) trở nên không khả thi để AC (Chứ cắn test vẫn tốt lắm :3 ) 

Giới hạn khác , cách tiếp cận cũng khác . Sau đây , mình xin giới thiệu phương pháp O(nlogn) sử dụng chặt nhị phân,

Giái:

Gọi H[i] là độ lớn  của phần tử thứ i của dãy con tăng.

VD : Có 2 dãy : 1, 2 ,3 , 

                           1, 2, 4

Hiển nhiên H[1]  = 1; H[2] = 2; H[3]  =  3.;

Việc này đồng nghĩa với việc gì ? 

+ Thứ nhất mình sẽ xây được cấu hình tối thiểu của dãy con tăng .Cấu hình tối thiểu là sao . Nó là dãy con tăng dài nhất mà các vị trí cũng đạt được min nhất có thể ( tại vị trí i = H[i] ). Nếu 1 phần tử mà xếp được  xếp vào được vị trí  thứ i  của dãy con này thì dãy con tăng dài nhất của nó cũng tương đương là i

+ Do các H đạt min nhất . Ta dễ nhận thấy H[1] <= H[2] <= .... <= ... ( nói chung là H[i] < H[i+1]  :3 )

Vì nếu có H[i] > H[i+1] ==> H[i] chưa đạt min 

Dựa vào điều kiện đó : Ta hoàn toàn có thể chặt nhị phân để tìm vị trí i lớn nhất mà phần tử thứ j có thể đạt tới hay LIS[j] = i.

Dưới đây là link bài LIS : http://vn.spoj.com/problems/LIS/

Và mình đã có solution bằng C++:http://ideone.com/K5dfcM

Hi vọng điều này sẽ giúp được các bạn :3