Tutorial — Khử Số

Khi một số nguyên dương bị biến đổi thành $0$, để dãy số không giảm thì toàn bộ các số $0$ phải nằm ở một tiền tố liên tục của dãy. Nếu một phần tử đứng trước lớn hơn phần tử đứng ngay sau nó, phần tử đứng trước bắt buộc phải được chuyển về $0$.

Mỗi thao tác gán $0$ sẽ áp dụng lên tất cả các vị trí có cùng giá trị trong toàn bộ dãy số. Do đó, nếu một giá trị trong tiền tố cần xóa xuất hiện thêm ở một vị trí xa hơn về phía sau, ta buộc phải mở rộng tiền tố cần xóa đến vị trí đó để duy trì tính chất các số $0$ luôn nằm ở đầu.

Hãy tìm vị trí nghịch thế cuối cùng của dãy ban đầu và lưu lại vị trí xuất hiện cuối cùng của từng phần tử bằng một mảng. Sau đó, duyệt một lượt từ đầu dãy để vừa mở rộng ranh giới cần gán về $0$ vừa đếm số lượng giá trị phân biệt xuất hiện trong ranh giới đó.