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.