Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

有一個長度為 $n$ 的陣列 $a$,其中第 $i$ 個數為 $a_i$。此外,每個數都有一個得分,第 $i$ 個數的得分為 $c_i$。Alice 和 Bob 輪流進行遊戲,Alice 先手。

在當前輪中,玩家首先將陣列 $a$ 複製到陣列 $b$,並執行一個隨機洗牌程式來隨機打亂陣列 $b$。具體來說,隨機洗牌程式會以相等機率選擇 $b$ 的排列之一,並用其替換原陣列 $b$。假設當前陣列 $a$ 的長度為 $m$,那麼玩家可以選擇一個整數 $k$,滿足 $0 \le k \le m$ 且 $a[1 \dots k] = b[1 \dots k]$,然後刪除 $a[1 \dots k]$(即 $a$ 的長度為 $k$ 的前綴)並獲得被刪除數字的得分。當陣列 $a$ 被清空時,遊戲結束。

注意,在整個過程中,陣列 $a$ 及其得分陣列 $c$ 不會被打亂,而只是它們的前綴會被移除。

Alice 和 Bob 都希望最大化自己的得分。Alice 想知道當雙方都採取最佳策略時,她的期望得分是多少。

Alice 還進行了 $q$ 組修改(修改陣列和得分),她希望你求出初始陣列的答案,以及每組修改之後的答案。

輸入格式

第一行包含一個整數 $n$($1 \le n \le 10^6$),表示初始陣列 $a$ 的長度。

第二行包含 $n$ 個整數 $a_1, a_2, \dots, a_n$($1 \le a_i \le n$),表示初始陣列 $a$。

第三行包含 $n$ 個整數 $c_1, c_2, \dots, c_n$($1 \le c_i \le 10^6$),表示陣列中每個數的得分。

下一行包含一個整數 $q$($0 \le q \le 10$),表示修改的組數。

接下來描述 $q$ 組修改:

對於每組修改,第一行包含 $k_i$($1 \le k_i \le 10^5$),表示該組中的修改次數。

接下來的 $k_i$ 行,每行包含三個整數 $p_j, x_j, y_j$($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$),表示將 $a_{p_j}$ 修改為 $x_j$,並將 $c_{p_j}$ 修改為 $y_j$。

保證 $p_1 < p_2 < \dots < p_{k_i}$。

輸出格式

輸出共 $q + 1$ 行,每行包含一個浮點數,表示答案。

第一行是初始陣列的答案,隨後是 $q$ 行,表示每組修改之後的答案。

如果你的答案與標準答案相比,相對誤差或絕對誤差不超過 $10^{-9}$,則視為正確。

範例

輸入格式 1

2
1 2
1 1
2
1
2 1 2
1
1 1 2

輸出格式 1

1.333333333333
3.000000000000
4.000000000000

輸入格式 2

6
1 1 4 5 1 4
2 3 3 3 3 3
0

輸出格式 2

9.013888888889

說明

本題輸入資料量較大,請使用高效的輸入方式。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.