Tác giả: DangHung845

• Subtask 1: Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thoả mãn: ~N \le 100~.

  Duyệt các xâu con liên tiếp. Với mỗi xâu con liên tiếp, duyệt đếm số lượng chữ cái mỗi loại, sau đó tính hàm ~F~ rồi so sánh với ~K~.

  Độ phức tạp: ~O(N^3)~

• Subtask 2: ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~N \le 1000~.

  Duyệt lần lượt theo thứ tự đầu trái tăng dần, rồi đầu phải tăng dần. Duy trì mảng ~cnt[c]~ là số chữ cái ~c~ trong xâu hiện tại. Dễ thấy khi chuyển sang xâu con tiếp theo, ta chỉ cần cập nhật lại một vị trí trong ~cnt[c]~. Lúc tính kết quả ta chỉ cần tính tổng bình phương số lượng của ~26~ chữ cái như yêu cầu.

  Độ phức tạp: ~O(N^2 \times 26)~

• Subtask 3: ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~N \le 10 000~.

  Tương tự phần trên, tuy nhiên ở mỗi bước tính kết quả, vì chỉ có duy nhất một vị trí trong ~cnt[c]~ thay đổi, nên ta hoàn toàn tính được ngay kết quả mới từ kết quả cũ mà không cần tính lại từ đầu.

  Độ phức tạp: ~O(N^2)~

• Subtask 4: ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~N \le 200 000~.

  Nhận xét rằng nếu một từ an toàn thì tất cả các từ là xâu con liên tiếp của từ đó cũng an toàn. Do đó với mỗi ~l \in [ 1, N]~, ta chỉ cần tìm ~r~ lớn nhất sao cho xâu con liên tiếp ~S[l, r]~ là một từ an toàn. Việc này có thể thực hiện bằng tìm kiếm nhị phân, kết hợp sử dụng mảng tổng dồn để tính nhanh số lượng chữ cái có trong một xâu con. Kết quả lúc này là ~\sum(r - l + 1)~

  Độ phức tạp: ~O(N \log N \times 26)~

• Subtask 5: ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài: Không có ràng buộc gì thêm.

  Nhận xét rằng khi ~l~ tăng thì ~r~ cũng tăng, nên ta có thể sử dụng kỹ thuật hai con trỏ đế tối ưu độ phức tạp.

  Độ phức tạp: ~O(N)~