Hướng dẫn cho Tần suất lớn nhất trên đoạn
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Gom các phần tử bằng nhau
Vì dãy đã sắp xếp, những phần tử bằng nhau nằm trong cùng một đoạn liên tiếp. Gom chúng thành các nhóm. Với nhóm \(g\), lưu vị trí đầu start[g], vị trí cuối finish[g] và độ dài length[g]. Mỗi vị trí trong dãy cũng lưu nhóm chứa nó.
Xét truy vấn \([l,r]\). Nếu \(l,r\) thuộc cùng một nhóm, đáp án là \(r-l+1\). Nếu chúng thuộc hai nhóm khác nhau \(x,y\), đoạn cần hỏi gồm:
- Phần còn lại của nhóm trái, dài
finish[x] - l + 1. - Phần đầu của nhóm phải, dài
r - start[y] + 1. - Các nhóm trọn vẹn từ \(x+1\) đến \(y-1\).
Dựng Sparse Table truy vấn max trên length. Lấy max của hai phần ở biên và nhóm trọn vẹn dài nhất. Nếu \(x+1>y-1\), phần giữa rỗng và đóng góp \(0\).
Chứng minh
Mỗi giá trị thuộc đúng một nhóm vì dãy không giảm. Trong truy vấn, nhóm đó hoặc nằm trọn ở giữa, hoặc bị cắt ở một trong hai biên. Ba phần trên liệt kê đủ mọi khả năng. Lấy độ dài lớn nhất của chúng cho đúng tần suất lớn nhất.
Độ phức tạp
Gọi \(G\le n\) là số nhóm. Gom nhóm tốn \(O(n)\); dựng bảng tốn \(O(G\log G)\) thời gian và bộ nhớ. Mỗi truy vấn tốn \(O(1)\).
Hai lời giải tham khảo C++ và Python đều dùng cách này. Python lưu các hàng chỉ tới vị trí bắt đầu còn hợp lệ. Với nhiều bộ test, cần dựng lại các nhóm và bảng cho từng bộ; không gộp tần suất của hai bộ test.
Bình luận