Tổng median
Đề bài
Mô tả
Bạn cần duy trì một tập hợp các số nguyên dương (ban đầu rỗng), hỗ trợ ba loại thao tác:
add x— thêm phần tử vào (đảm bảo chưa có trong ).del x— xóa phần tử khỏi (đảm bảo đang có trong ).sum— tính tổng các phần tử "median" của .
Sau khi sắp xếp tăng dần thành dãy , tổng median được định nghĩa là tổng của các với , tức là . Nếu rỗng, tổng median bằng .
Dữ liệu vào
- Dòng đầu chứa số nguyên — số thao tác.
- dòng sau, mỗi dòng mô tả một thao tác theo định dạng trên.
Dữ liệu ra
Với mỗi thao tác sum, in ra một dòng chứa tổng median tương ứng.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 add 4 add 5 add 1 add 2 add 3 sum |
3 | Sau khi thêm, . Vị trí là . Tổng = 3. |
| 14 add 1 add 7 add 2 add 5 sum add 6 add 8 add 9 add 3 add 4 add 10 sum del 1 sum |
5 11 13 |
Lần sum đầu: , . Lần thứ hai: , . Sau khi xóa 1: , . |
Bình luận