Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

C'è un array $a$ di lunghezza $n$, dove l'$i$-esimo numero è $a_i$. Inoltre, ogni numero ha un punteggio, e il punteggio dell'$i$-esimo numero è $c_i$. Alice e Bob giocano a turno, e Alice inizia per prima.

Nel turno corrente, il giocatore copia prima l'array $a$ nell'array $b$ ed esegue un programma di mescolamento casuale per mescolare casualmente l'array $b$. Nello specifico, il programma di mescolamento casuale selezionerà una delle permutazioni di $b$ con uguale probabilità e sostituirà l'array originale $b$ con essa. Supponiamo che la lunghezza attuale dell'array $a$ sia $m$; allora il giocatore può scegliere un intero $k$ tale che $0 \le k \le m$ e $a[1 \dots k] = b[1 \dots k]$, e quindi eliminare $a[1 \dots k]$ (cioè il prefisso di lunghezza $k$ di $a$) e ottenere il punteggio dei numeri eliminati. Il gioco termina quando l'array $a$ viene svuotato.

Si noti che l'array $a$ e il suo array dei punteggi $c$ non verranno mescolati durante l'intero processo, ma verranno rimossi solo i loro prefissi.

Sia Alice che Bob vogliono massimizzare i propri punteggi. Alice vuole sapere qual è il suo punteggio atteso quando entrambi i giocatori adottano strategie ottimali.

Alice ha anche effettuato $q$ gruppi di modifiche (modificando l'array e i punteggi), e vuole che tu trovi la risposta per l'array iniziale, così come le risposte dopo ogni gruppo di modifiche.

Input

La prima riga contiene un intero $n$ ($1 \le n \le 10^6$), che rappresenta la lunghezza dell'array iniziale $a$.

La seconda riga contiene $n$ interi $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), che rappresentano l'array iniziale $a$.

La terza riga contiene $n$ interi $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), che rappresentano il punteggio di ciascun numero nell'array.

La riga successiva contiene un intero $q$ ($0 \le q \le 10$), che rappresenta il numero di gruppi di modifiche.

Di seguito vengono descritti $q$ gruppi di modifiche:

Per ogni gruppo di modifiche, la prima riga contiene $k_i$ ($1 \le k_i \le 10^5$), che indica il numero di modifiche in questo gruppo.

Le successive $k_i$ righe contengono ciascuna tre interi $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), ad indicare che $a_{p_j}$ viene modificato in $x_j$ e $c_{p_j}$ viene modificato in $y_j$.

È garantito che $p_1 < p_2 < \dots < p_{k_i}$.

Output

Stampa un totale di $q + 1$ righe, ciascuna contenente un numero in virgola mobile che rappresenta la risposta.

La prima riga è la risposta per l'array iniziale, seguita da $q$ righe per le risposte dopo ogni gruppo di modifiche.

Una risposta è considerata corretta se l'errore relativo o assoluto rispetto alla risposta standard non supera $10^{-9}$.

Esempi

Input 1

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

Output 1

1.333333333333
3.000000000000
4.000000000000

Input 2

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

Output 2

9.013888888889

Note

Questo problema ha una dimensione di input elevata, si prega di utilizzare un metodo di input efficiente.

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.