← 返回题目列表

Codeforces · 626/G

G. 莱佛士

中文机器翻译题面 查看原题

约翰尼正在参加一个有 n 次抽奖活动的嘉年华。抽奖我有一个价值 pi 的奖品。每个参与者都可以将门票放入他们选择的任何抽奖活动中(他们可以在一次抽奖活动中拥有不止一张门票)。嘉年华结束时,每次抽奖都会随机抽取一张彩票,彩票拥有者将赢得相关奖品。一个人可以从不同的抽奖中赢得多个奖品。

但是,县规则禁止任何一个参与者在一次抽奖中拥有超过一半的彩票,即在抽奖中投入的彩票数量比所有其他参与者的总和还要多。为了帮助解决这个问题(并可能赢得一些奖品),组织者首先在每次抽奖中放置一张彩票,并且永远不会将其移除。

约翰尼买了 t 张票,不知道把它们放在哪里。目前,第i次抽奖共有li张票。他看着其他参与者买票并修改他们的决定,并且每时每刻都想知道他可能赚多少钱。如果约翰尼以最佳方式分配他的彩票,请找出他在每一时刻的奖金的最大可能期望值。约翰尼可以在每次更新之间任意重新分配他的所有门票,但他在一次抽奖中放置的门票总数不得超过 t 个,或者在一次抽奖中拥有的门票数量不得超过所有其他参与者的总和。

输入

第一行包含两个整数 n、t 和 q (1 ≤ n, t, q ≤ 200 000) — 分别是抽奖次数、Johnny 拥有的彩票数量和更新总数。

第二行包含 n 个空格分隔的整数 pi (1 ≤ pi ≤ 1000) — 第 i 个奖品的价值。

第三行包含 n 个空格分隔的整数 li (1 ≤ li ≤ 1000) — 第 i 次抽奖中最初的彩票数量。

最后 q 行包含更新的描述。每个描述包含两个整数 tk, rk (1 ≤ tk ≤ 2, 1 ≤ rk ≤ n) — 更新类型和抽奖号码。类型 1 的更新表示另一位参与者向抽奖 rk 添加门票。类型 2 的更新表示另一位参与者从抽奖 rk 中删除一张票。

保证每次更新后,每次抽奖中至少有1张彩票(不包括Johnny's)。

输出

打印 q 行,每行包含一个实数 - 第 k 次更新后约翰尼获胜的最大预期值。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。

即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。

示例

输入 #1

2 1 3
4 5
1 2
1 1
1 2
2 1

输出 #1

1.666666667
1.333333333
2.000000000

输入 #2

3 20 5
6 8 10
6 6 6
1 1
1 2
1 3
2 3
2 3

输出 #2

12.000000000
12.000000000
11.769230769
12.000000000
12.000000000

注意

在第一种情况下,Johnny 只有一张票可供分发。奖品价值 4 和 5,抽奖最初分别有 1 和 2 张门票。第一次更新后,每次抽奖都有 2 张门票,因此 Johnny 通过将其门票放入第二次抽奖,预计获胜价值为 $$\frac{5}{3}$$。第二次更新为第二次抽奖添加了一张门票,因此约翰尼可以在第一次抽奖中赢得 $$\frac{4}{3}$$。最终更新后,约翰尼在第一次抽奖中保留了他的彩票并赢得了 $$\frac{4}{2}$$。

在第二种情况下,Johnny 拥有的门票数量超出了他允许花费的数量。特别是,第一次更新后,每次抽奖分别有 7 张、6 张和 6 张门票,因此 Johnny 只能投入 19 张门票,以 $$\frac{1}{2}$$ 的概率赢得每份奖品。另请注意,在最后两次更新后,Johnny 必须从最后一次抽奖中删除一张彩票,以便将第三次抽奖中的彩票保留在 $$\frac{1}{2}$$ 之下。