Theo mình thì làm thế này. Với mỗi giá trị. Mình đếm số dãy tốt với giá trị xuất hiện nhiều hơn n/2 lần là giá trị đó, rồi sau đó cộng lại.
Giờ với bài toán nhỏ hơn. Cho dãy a gồm n phần tử, đếm số dãy có giá trị T xuấn hiện hơn n/2 lần:
- Đầu tiên, với giá trị nào = x thì gán nó lại thành 1. Giá trị nào khác x thì gán thành -1. Bài toán trở thành đếm số dãy con có tổng lớn hơn 0.
- Cập nhật cây bit để tính tổng.
- Gọi số số 1 của dãy này là H, bạn chạy con trỏ i từ trái qua, để đếm số dãy tốt kết thúc tại i bằng bit. Nếu vị trí nào mà có dãy tốt thì tăng i lên 1. Không có thì di chuyển i đến vị trí phía sau gần i nhất có giá trị là 1. Như vậy thì ta có thể chứng minh luôn được là số lần i di chuyển không quá 2*H.
- Độ phức tạp của bài toán con là 2*H*log.
- Kết hợp lại thì ta sẽ có thuật giải n*log.
- Lưu ý là bước chuyển từ bài toán này sang bài toán kia. Bạn ko chạy lại hoàn toàn bước 1 và 2 mà chỉ chạy lại trên các vị trí thay đổi. Nên chi phí chuyển cũng là n log luôn.