Yêu cầu:
Hãy quản lí một tập hợp các số nguyên không âm hỗ trợ các thao tác sau:
- Thêm một phân tử
- Xóa một phần tử
- Tìm trung vị của tập hợp
Định nghĩa trung vị:
Trung vị của dãy ~a[1 \dots N]~ được sắp xếp không giảm là phần tử ~a\left[\frac{N + 1}{2}\right]~.
Input
Dòng đầu tiên chứa ~Q~ là số truy vấn. ~( 1 \leq Q \leq 10^{6} )~
~Q~ dòng tiếp theo, mỗi dòng gồm một kí tự '+' hoặc '-' và một số nguyên không âm nhỏ hơn ~10^9~. Dấu '+' biểu thị thao tác thêm phần tử ~x~ vào tập hợp (có thể tập hợp đã có phần tử ~x~ nhưng thao tác này vẫn được thực hiện). Dấu '-' biểu thị thao tác xóa phần tử ~x~ khỏi tập hợp (bộ test đảm bảo tồn tại phần tử ~x~ trong tập hợp).
Output
~Q~ dòng, mỗi dòng là trung vị của tập hợp sau mỗi thao tác thêm/xóa.
Sample Input
20
+ 6
+ 2
+ 5
+ 3
+ 6
- 3
+ 8
- 6
- 5
+ 5
+ 2
- 8
+ 5
+ 5
- 2
+ 1
- 5
+ 4
+ 8
+ 7
Sample Output
6
2
5
3
5
5
6
5
6
5
5
2
5
5
5
5
5
4
5
5
Note
~\begin{array}{lll} \mbox{Input} & \mbox{Output} & \mbox{Explanation} \\ 20 & 6 & {[}6{]} \\ +6 & 2 & {[}2, 6{]} \\ +2 & 5 & {[}2, 5, 6{]} \\ +5 & 3 & {[}2, 3, 5, 6{]} \\ +3 & 5 & {[}2, 3, 5, 6, 6{]} \\ +6 & 5 & {[}2, 5, 6, 6{]} \\ -3 & 6 & {[}2, 5, 6, 6, 8{]} \\ +8 & 5 & {[}2, 5, 6, 8{]} \\ -6 & 6 & {[}2, 6, 8{]} \\ -5 & 5 & {[}2, 5, 6, 8{]} \\ +5 & 5 & {[}2, 2, 5, 6, 8{]} \\ +2 & 2 & {[}2, 2, 5, 6{]} \\ -8 & 5 & {[}2, 2, 5, 5, 6{]} \\ +5 & 5 & {[}2, 2, 5, 5, 5, 6{]} \\ +5 & 5 & {[}2, 5, 5, 5, 6{]} \\ -2 & 5 & {[}1, 2, 5, 5, 5, 6{]} \\ +1 & 5 & {[}1, 2, 5, 5, 6{]} \\ -5 & 4 & {[}1, 2, 4, 5, 5, 6{]} \\ +4 & 5 & {[}1, 2, 4, 5, 5, 6, 8{]} \\ +8 & 5 & {[}1, 2, 4, 5, 5, 6, 7, 8{]} \\ +7 & & \end{array}~
Bình luận
Nếu tập hợp rỗng thì xuất ra gì nhỉ :v ?
Bạn đọc kĩ đề nhé
cảm ơn bạn
Lời giải của Team mình, lưu ý chỉ nên xem khi đã bí cách cũng như bất lực để việc học hiệu quả.
Unofficial Solution: