#523. 「多校联考 Round 3」集合

内存限制:512 MiB 时间限制:1000 ms 输入文件:set.in 输出文件:set.out
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

本题中,我们规定 \max(S) 表示 S 中最大的数, \text{mean}(S) 表示 S 中所有数的平均数。

小 Y 和小 H 是一对好朋友,这一天,他们正在讨论一道 OI 题目:

  • 维护一个可重集合 S ,支持插入一个数 x ,或者查询 \max(S) - \text{mean}(S)

小 H 一眼就把这道题秒了。小 Y 见到他洋洋得意的样子,想给他个下马威,于是她反手把题目改成了这个样子,并上传到了学校的 OJ 上:

  • 维护一个可重集合 S ,支持插入一个数 x ,或者找出集合的一个子集 S' \subseteq S ,使得 \max(S') - \text{mean}(S') 最大。

小 H 傻眼了,在罚坐了两个小时后,他依然不知道该怎么做,但是他又不想被小 Y 笑话。

小 H 作为学校 OJ 的管理员,能够修改题目的数据。但他不能做的太过明显,不然小 Y 就会发现。于是,小 H 偷偷把题目中插入的 x 升序排序,这样做既降低了题目难度,又不会让小 Y 发现。

然而,小 H 发现弱化后的题目他依然不会做!他只好找到你,请你帮助他解决这道弱化过的题目,不至于让他被小 Y 笑话。

输入格式

第一行一个正整数 Q ,表示操作次数。

接下来 Q 行,每行描述一个操作:

  • 1 x:插入 x S

  • 2:找出集合的一个子集 S' \subseteq S ,使得 \max(S') - \text{mean}(S') 最大,并输出这个数。

输出格式

对于每个 2 操作,输出一行一个实数,表示答案。你的答案跟标准答案相差不超过 10^{-6} 时被认为是正确的。

样例

样例输入 1

6
1 3
2
1 4
2
1 8
2

样例输出 1

0.0000000000
0.5000000000
3.0000000000

样例输入 2

4
1 1
1 4
1 5
2

样例输出 2

2.0000000000

数据范围与提示

对于所有数据, 1 \le Q \le 5 \times 10^5, 1 \le x \le 10^9 ,保证输入的 x 递增 x 为整数。

每个测试点的详细范围见下表:

测试点编号 Q = 特殊性质
1 \sim 4 10
5 \sim 8 2000
9 \sim 12 499997 保证 2 操作只有一次
13 \sim 16 499998 保证 2 操作不超过 2000
17 \sim 20 499999 保证对于第 i 1 操作, x=i
21 \sim 25 500000