CF85D Sum of Medians

在一种著名的第 $k$ 小值查找算法中，需要将所有元素分成连续的五个一组，并找到每组五个元素的中位数。中位数指的是一个有序数组的中间元素（对于一个五个元素的组来说，就是五个的元素中的第三大）。为了提升该算法的运算效率，你需要能够求出数组中每五个元素的中位数的和。 已排序的 $k$ 元素集合 $S = \{a_1, a_2, ..., a_k\}$ 的中位数和定义为： $$ \sum_{i \bmod 5 = 3}^{i \le k} a_i. $$ 其中，$\bmod$ 运算符表示取余，即 $x \bmod y$ 表示 $x$ 除以 $y$ 的余数。 现需支持高效地对变动集合求中位数和的操作。

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示操作次数。 接下来每行描述一种操作，共 $n$ 行，操作有三种： - add $x$ —— 向集合中加入元素 $x$； - del $x$ —— 从集合中删除元素 $x$； - sum —— 输出当前集合所有五元组的中位数之和。 对于任一 add $x$ 操作，保证操作前 $x$ 不在集合中。 对于任一 del $x$ 操作，保证操作前 $x$ 在集合中。 输入中的所有数字均为正整数，且不超过 $10^9$。

对于每个 sum 操作，输出当前集合中所有五元组的中位数之和。如果集合为空，输出 $0$。 请勿在 C++ 中使用 %lld 读写 64 位整数。建议使用 cin、cout 流（也可以使用 %I64d）。

由 ChatGPT 5 翻译