Xếp Chồng

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

1. 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·K)$ quá chậm với $N\le {10}^6$.
2. 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.
3. Sau khi có mảng chiều cao, sắp xếp và lấy phần tử ở vị trí $\lceil N/2\rceil$ (vị trí giữa, $N$ lẻ).

Thuật toán

1. Khởi tạo mảng hiệu diff[1..N+1] = 0.
2. Với mỗi thao tác $(A_i,B_i)$: diff[A_i]++, diff[B_i+1]--.
3. Tính prefix sum: height[i] = height[i-1] + diff[i] để ra chiều cao của từng ngăn.
4. Sắp xếp mảng height.
5. 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)$