Các giải pháp lấy điểm thành phần

• Giải pháp \(O(N^2)\): xét mọi \(l,r\) là biên trái và biên phải của đoạn con. Chỉ cần kiểm tra phần tử xuất hiện nhiều nhất trong đoạn con xem nó có xuất hiện ít nhất \(\left( \left\lfloor \dfrac{r-l+1}{2}+1 \right\rfloor \right)\) lần hay không. Khi thay đổi cận phải, cập nhật tần suất của phần tử mới chèn trong một mảng tần suất. Phần tử có tần suất cao nhất sẽ là hoặc phần tử nhiều nhất trước đó hoặc phần tử vừa chèn (quyết định dựa trên giá trị trong mảng tần suất).
• Giải pháp \(O(N⋅|V|)\): \(V\) là tập giá trị khác nhau trong dãy \(A\) ban đầu. Chọn \(X\) là một phần tử trong \(V\). Mục tiêu là đếm trong \(O(N)\) có bao nhiêu dãy con mà \(X\) là số chính.
  • Bước 1: Xây dựng mảng phụ \(B\) kích thước \(N\) theo quy tắc: \(A[i]=X⟹B[i]=1;A[i]≠X⟹B[i]=-1\)
  • Bước 2: Tính mảng tổng tiền tố: \(S[i]=B[1]+B[2]+⋯+B[i] (S[0]=0)\).
  • Bước 3: Với mỗi cận phải \(R\) cố định, cần đếm số giá trị \(L≥0\) sao cho \(S[R]-S[L]>0\). Ta có sử dụng fenwick tree (thêm hệ số \(log⁡N\)) hoặc tận dụng đặc điểm \(S[R]\) chỉ sai khác \(S[R-1]\) một lượng \(±1\) cập nhật kết quả cho \(R\) từ kết quả cho \(R-1\) .
• Giải pháp \(O(N⋅√N)\): Chia các phần tử thành hai nhóm:
  • Nhóm tần suất \(<√N\): những phần tử này không thể chiếm ưu thế trong dãy có độ dài \(>2√N\), có thể xử lý brute-force.
  • Nhóm tần suất \(≥√N\): số phần tử khác nhau tối đa là \(√N\), với mỗi phần tử trong nhóm này áp dụng thuật toán \(O(N⋅|V|)\) ở trên.
  • Ngoài ra còn nhiều biến thể \(O(N⋅√N)\) khác, chẳng hạn ứng dụng thuật toán Mo kết hợp brute-force cho các dãy ngắn và giữ 2–3 phần tử xuất hiện nhiều nhất trong mỗi khối.

Giải pháp chia để trị

Chia miền \([L;R]\) thành hai nửa \([L,M]\) và \([M+1,R]\). Đệ quy đếm số đoạn con tốt (đoạn con có số chính) trên mỗi nửa.
Vấn đề là phần “kết hợp”: đếm số đoạn con tốt \([l,r]\) bắt đầu ở nửa trái \((l≤M)\) và kết thúc ở nửa phải \((M<r)\).
Giả sử \(v\) là số chính của một đoạn con tốt \([l,r]\) như mô tả trên, thế thì \(v\) phải là số chính của ít nhất một trong hai đoạn \([l,M]\) và \([M+1,r]\). Ta gọi một \(v\) là số chính của một đoạn \([l,M],[M+1,r]\) nào đó là các ứng cử viên (candidate).
Xét quá trình mở rộng, chẳng hạn, đoạn \([M,r]\) về bên phải, một ứng cử viên mới xuất hiện đồng nghĩa độ dài đoạn phải tăng gấp đôi. Điều này có nghĩa là tổng số lượng ứng cử viên không thể vượt quá log⁡N.
Từ nhận xét này, ta có thể duyệt qua hai nửa, ghi nhận danh sách các ứng viên. Sau đó xét từng ứng viên, áp dụng giải thuật đếm theo tiền tố/hậu tố \(O(N⋅|V|)\) ở trên.
Chi phí kết hợp là \(O(N log⁡N )\). Giải pháp đạt độ phức tạp tổng thể \(O(N log^2⁡N )\).