Universal Cup Judging System

Universal Cup

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

Det finns en array $a$ av längd $n$, där det $i$-te talet är $a_i$. Dessutom har varje tal en poäng, och poängen för det $i$-te talet är $c_i$. Alice och Bob turas om, och Alice börjar.

I den aktuella rundan kopierar spelaren först arrayen $a$ till arrayen $b$ och kör ett slumpmässigt blandningsprogram för att slumpmässigt blanda arrayen $b$. Mer specifikt väljer blandningsprogrammet en av permutationerna av $b$ med lika sannolikhet och ersätter den ursprungliga arrayen $b$ med den. Antag att den aktuella längden på arrayen $a$ är $m$; då kan spelaren välja ett heltal $k$ sådant att $0 \le k \le m$ och $a[1 \dots k] = b[1 \dots k]$, och sedan ta bort $a[1 \dots k]$ (dvs. prefixet av längd $k$ av $a$) och få poängen för de borttagna talen. Spelet slutar när arrayen $a$ är tömd.

Observera att arrayen $a$ och dess poängarray $c$ inte blandas under hela processen, utan endast deras prefix tas bort.

Både Alice och Bob vill maximera sina poäng. Alice vill veta vad hennes förväntade poäng är när båda spelarna använder optimala strategier.

Alice gjorde också $q$ grupper av modifieringar (som ändrar arrayen och poängen), och hon vill att du hittar svaret för den ursprungliga arrayen samt svaren efter varje grupp av modifieringar.

Indata

Den första raden innehåller ett heltal $n$ ($1 \le n \le 10^6$), som representerar längden på den ursprungliga arrayen $a$.

Den andra raden innehåller $n$ heltal $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), som representerar den ursprungliga arrayen $a$.

Den tredje raden innehåller $n$ heltal $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), som representerar poängen för varje tal i arrayen.

Nästa rad innehåller ett heltal $q$ ($0 \le q \le 10$), som representerar antalet grupper av modifieringar.

Följande beskriver $q$ grupper av modifieringar:

För varje grupp av modifieringar innehåller den första raden $k_i$ ($1 \le k_i \le 10^5$), vilket anger antalet modifieringar i denna grupp.

De följande $k_i$ raderna innehåller var och en tre heltal $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), vilket anger att $a_{p_j}$ ändras till $x_j$ och $c_{p_j}$ ändras till $y_j$.

Det garanteras att $p_1 < p_2 < \dots < p_{k_i}$.

Utdata

Skriv ut totalt $q + 1$ rader, där varje rad innehåller ett flyttal som representerar svaret.

Den första raden är svaret för den ursprungliga arrayen, följt av $q$ rader för svaren efter varje grupp av modifieringar.

Ett svar betraktas som korrekt om det relativa eller absoluta felet jämfört med standardsiffran inte överstiger $10^{-9}$.

Exempel

Indata 1

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

Utdata 1

1.333333333333
3.000000000000
4.000000000000

Indata 2

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

Utdata 2

9.013888888889

Notering

Detta problem har en stor indatastorlek, använd gärna en effektiv inläsningsmetod.

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.