Hướng dẫn giải của Trên Trung Vị

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

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

Hướng tiếp cận

Đếm số mảng con có trung vị $\geq 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

Trung vị của mảng con $\geq X$ khi và chỉ khi số phần tử $\geq X$ nhiều hơn số phần tử $< X$ .
Biến đổi: $b_{i} = + 1$ nếu $a_{i} \geq X$ , $b_{i} = - 1$ nếu $a_{i} < X$ .
Mảng con $[l, r]$ có trung vị $\geq X$ $\Leftrightarrow$ tổng $b_{l} + b_{l + 1} + \dots + b_{r} \geq 0$ .
Dùng tiền tố $S_{j} = b_{1} + \dots + b_{j}$ : điều kiện trở thành $S_{r} \geq S_{l - 1}$ .

Thuật toán

Đếm số cặp $(l - 1, r)$ với $0 \leq l - 1 < r \leq n$ sao cho $S_{r} \geq 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} \geq 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)$

Bình luận

Không có bình luận tại thời điểm này.