Đặt f(i,x) là dãy con có độ dài bé nhất mà các số từ 1 đến x xuất hiện ít nhất 1 lần và có đầu phải là i.
Nhận xét 1: Nếu 1 dãy thỏa mãn x thì sẽ luôn thỏa cho x−1.
Vậy ta sẽ tìm f(i,x) từ f(i,x−1) cho mọi i.
Đặt g(i,x) là vị trí j lớn nhất mà j..i là một dãy đầy đủ cho x. Hay f(i,x)=i−g(i,x)+1 (*).
Giả sử ta đã có các f(i,x) , thì với mỗi vị trí xuất hiện idx của x+1 và vị trí xuất hiện tiếp theo idx2 về bên phải idx của x+1, nó sẽ thay đổi giá trị của các f(j,x) thỏa mãn idx≤j≤idx2−1
Ta thấy với mỗi idx thì nó cũng sẽ thay đổi g(i,x) tương ứng. Cụ thể hơn là g(j,x+1)=min(g(j,x),idx) với idx≤j≤idx2.
Nhận xét 2: Ta luôn có g(i,x)≤g(i+1,x).
Từ nhận xét 2, gọi next là vị trí bé nhất mà g(next,x)≥idx thì ta sẽ có thể cập nhật g(j,x+1)=idx cho các vị trí next≤j≤idx2.
Bước này ta có thể tìm next bằng cách dùng kĩ thuật walk on tree theo nhận xét 2.
Ở đây ta có thể dùng cây phân đoạn (segment tree) để quản lý các g(i,x) và tính f(i,x).
Ta sẽ có thao tác cập nhật 1 đoạn thành 1 giá trị (cập nhật g(i,x) như ở trên). Với mỗi đoạn (l,r) có giá trị bằng nhau(tức g(i,x)) trên segment tree thì ta có thể tham lam lấy ngay min f(i,x) với l≤i≤r=l+1− (giá trị của node) . (Theo công thức (*)).
Gọi lim=max(vị trí nhỏ nhất cho từng giá trị 1 đến x) thì ta sẽ truy vấn trên cây segment tree để lấy min f(i,x) với lim≤i≤n.
Nếu không tồn tại giá trị x thì mọi f(i,y)=−1 với mọi 1≤i≤n và y≥x.
Nếu bạn nào còn thắc mắc thì có thể dm trực tiếp cho mình.
lenhanbo
Created at
12 likes