Trên Trung Vị

Lời giải: Trên Trung Vị

Hướng tiếp cận

Đếm số mảng con có trung vị $\ge X$. Thay vì xét trung vị trực tiếp, ta biến đổi mảng và sử dụng kỹ thuật tiền tố.

Nhận xét quan trọng

1. Trung vị của mảng con $\ge X$ khi và chỉ khi số phần tử $\ge X$ nhiều hơn số phần tử $<X$.
2. Biến đổi: $b_i=+1$ nếu $a_i\ge X$, $b_i=-1$ nếu $a_i<X$.
3. Mảng con $[l,r]$ có trung vị $\ge X$ $\iff$ tổng $b_l+b_{l+1}+\cdots +b_r\ge 0$.
4. Dùng tiền tố $S_j=b_1+\cdots +b_j$: điều kiện trở thành $S_r\ge S_{l-1}$.

Thuật toán

Đếm số cặp $(l-1,r)$ với $0\le l-1<r\le n$ sao cho $S_r\ge S_{l-1}$.

Tổng số mảng con = $\frac{n(n+1)}{2}$. Ta trừ đi số mảng con có tổng âm (tức $S_r<S_{l-1}$).

Duy trì mảng đếm tần suất các giá trị tiền tố đã gặp. Khi xử lý phần tử mới:

• Nếu $a_j\ge X$: tăng $S$, số cặp xấu mới = số tiền tố cũ bằng đúng $S$ mới (vì chúng lớn hơn $S$ hiện tại).
• Nếu $a_j<X$: giảm $S$, số cặp xấu mới = số tiền tố cũ bằng đúng $S$ cũ (vì $S$ cũ > $S$ mới).

Độ phức tạp

• Thời gian: $O(N)$
• Bộ nhớ: $O(N)$