配点 : 1400 点
故事
“……我喜欢你”
这是伊吕波酱在回家路上交给我的一封信。信封用可爱的爱心贴纸封着。\r\n里面放着这样一道题。
“伊吕波酱,果然你才是真正的最终 Boss……”
問題文
※“平吉”是举办本次竞赛的人名。此外,平吉君并不是伊吕波酱。
在伊吕波界,伊吕波酱在数轴上放置或消除万个硬币,是一件众所周知的事。
起初,数轴上一个硬币也没有。
伊吕波酱将Q 次操作依次进行。操作如下。 3 种类。
- 追加操作:数轴上的坐标 x 至 通过 v 放置一枚圆形硬币。但是,坐标 x 保证在此时没有放置任何硬币。
- 删除操作:数轴上的坐标 x 删除位于坐标 x 处的硬币。但是,保证在此时坐标
- 指令操作:将小明放置在坐标 x 处,并让他取走一枚硬币。此时,小明一定会取走使“效率”最大化的硬币。此外,位于坐标 c 处的 w 取圆形硬币时的“效率”是 \frac{w}{|c-x|} 。在这里,|t| 是 t 的绝对值。
例如,坐标 2 至 通过 3 处有圆形硬币,坐标 5 至 通过 8 处有硬币时,各种情况下效率的最大值如下所示。
- 当平吉君位于坐标 0 处时,平吉君会取走“效率”最大的坐标 5 处的硬币,“效率”的值为 1.6
- 当平吉君位于坐标 1 处时,平吉君会取走“效率”最大的坐标 2 处的硬币,“效率”的值为 3.0
- 当平吉君位于坐标 7 处时,平吉君会取走“效率”最大的坐标 5 处的硬币,“效率”的值为 4.0
但是请注意,通过指令取走的硬币会在伊吕波酱的手腕作用下立即回到原来的位置,因此平吉君可能会取走同一枚硬币两次以上。
请依次求出对于每条指令,平木君移动过程中的“效率”值。
但是,在执行指令时,如果此时数轴上不存在硬币,则“效率”的值为 0 将变为。
制約
- 所有输入均为整数
- 1\leq Q\leq3 \times 10^5
- 0\leq x\leq10^9
- 0\leq v\leq10^9
- 在所有添加操作中,要添加硬币的坐标在该时刻没有放置硬币
- 在所有消除操作中,要消除硬币的坐标在该时刻放置有硬币
- 在所有命令中,执行命令时,Hirakichi君所在的坐标上都没有放置硬币
部分点
在这道题中,部分分如下所示。
- Q \leq 120000 对所有满足条件的测试用例都答对后,1100 点。 如果您正确回答
- 如果全部测试用例都答对,此外 300 点。 如果您正确回答
入力
输入将以以下格式从标准输入 Q + 1 跨多行给出。
Q (1 個目の操作の情報) (2 個目の操作の情報) (3 個目の操作の情報) ... (Q 個目の操作の情報)
在追加操作的情况下,该行输入如下。
1 x v
在删除操作的情况下,该行输入如下。
2 x
在命令操作的情况下,该行输入如下。
3 x
出力
对于所有命令术,请输出 HIRAKICHI 君最优动作中“效率”的最大值 按顺序 请输出。
绝对论文或相对论文 10^{-5} 以内是允许的。
入力例 1
11 1 2 3 3 10 1 5 8 3 0 3 1 3 7 2 2 1 7 9 3 3 3 6 3 10
出力例 1
0.375000000000 1.600000000000 3.000000000000 4.000000000000 4.000000000000 9.000000000000 3.000000000000
入力例 2
10 1 0 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9
出力例 2
10.000000000000 5.000000000000 3.333333333333 2.500000000000 2.000000000000 1.666666666667 1.428571428571 1.250000000000 1.111111111111