Đặ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 \le j \le 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 \le j \le idx2$.
Nhận xét $2$: Ta luôn có $g(i,x) \le g(i + 1,x)$.
Từ nhận xét $2$, gọi next là vị trí bé nhất mà $g(next,x) \ge idx$ thì ta sẽ có thể cập nhật $g(j,x+1) = idx$ cho các vị trí $next \le j \le 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 \le i \le r$ $ = l + 1 - $ (giá trị của node) . (Theo công thức (*)).
Gọi $lim = max(\text{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 \le i \le n$.
Nếu không tồn tại giá trị $x$ thì mọi $f(i,y) = -1$ với mọi $1 \le i \le n$ và $y \ge 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
9 likes