Hướng dẫn giải của Xếp Chồng

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: Ngăn Xếp

Hướng tiếp cận

Dùng mảng hiệu (difference array) để tính chiều cao của $N$ ngăn xếp sau $K$ thao tác trong $O (N + K)$ , sau đó sắp xếp và lấy phần tử ở vị trí giữa.

Nhận xét quan trọng

Mỗi thao tác tăng tất cả ngăn trong đoạn $[A, B]$ lên 1. Nếu dùng vòng lặp trực tiếp thì $O (N \cdot K)$ quá chậm với $N \leq 10^{6}$ .
Mảng hiệu cho phép xử lý thao tác tăng đoạn trong $O (1)$ : diff[A]++, diff[B+1]--. Sau đó tính prefix sum để ra chiều cao thực.
Sau khi có mảng chiều cao, sắp xếp và lấy phần tử ở vị trí $⌈ N / 2 ⌉$ (vị trí giữa, $N$ lẻ).

Thuật toán

Khởi tạo mảng hiệu diff[1..N+1] = 0.
Với mỗi thao tác $(A_{i}, B_{i})$ : diff[A_i]++, diff[B_i+1]--.
Tính prefix sum: height[i] = height[i-1] + diff[i] để ra chiều cao của từng ngăn.
Sắp xếp mảng height.
Kết quả là height[(N+1)/2] (vị trí giữa, 1-indexed).

Độ phức tạp

Thời gian: $O ((N + K) + N \log N)$
Bộ nhớ: $O (N)$

Bình luận

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