Dãy con có liên tiếp không bạn?

cho mình hỏi ở đây dãy con tốt có nghĩa là trong dãy con đó xuất hiện 1 giá trị nhiều hơn N/2 lần hay là trong dãy con đó xuất hiện 1 giá trị nhiều hơn (độ dài dãy con ) div 2

Xây dựng 1 cái vector d. d[x] lưu tập các chỉ số x trong a tăng dần, Duyệt rồi chặt đếm thôi. dpt O(nlogn) chắc vẫn qua :D

Bạn nói rõ hơn làm thế nào mà nlogn nhỉ, mình chưa hình dung được

Giả sử có 1 vecor x lưu tập các chỉ số mà x xuất hiện hiện trong dãy a[]

Với mỗi cặp  chỉ số trong x thì có 1 dãy con, nếu dãy con này thỏa thì có nghĩa là có thể tồn tại dãy con mới bằng cách mở rộng sang trái hoặc phải của dãy con cũ. Vì số lượng só cặp tỷ lệ nghịch với số phân tử khác nhau của a[] nên mình nghĩ là qua. Còn đây chắc chưa phải cách tối ưu

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. 

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. 

Mình dùng danh sách liên kết để chạy theo giá trị T (T=1..k) đúng không anh?

Còn chỗ cập nhật cây bit thì làm thế nào ạ?