Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

Hay un arreglo $a$ de longitud $n$, donde el $i$-ésimo número es $a_i$. Además, cada número tiene una puntuación, y la puntuación del $i$-ésimo número es $c_i$. Alice y Bob toman turnos, comenzando Alice primero.

En la ronda actual, el jugador primero copia el arreglo $a$ en el arreglo $b$ y ejecuta un programa de mezcla aleatoria para barajar aleatoriamente el arreglo $b$. Específicamente, el programa de mezcla aleatoria seleccionará una de las permutaciones de $b$ con igual probabilidad y reemplazará el arreglo original $b$ con ella. Supongamos que la longitud actual del arreglo $a$ es $m$; entonces el jugador puede elegir un entero $k$ tal que $0 \le k \le m$ y $a[1 \dots k] = b[1 \dots k]$, y luego eliminar $a[1 \dots k]$ (es decir, el prefijo de longitud $k$ de $a$) y obtener la puntuación de los números eliminados. El juego termina cuando el arreglo $a$ queda vacío.

Observa que el arreglo $a$ y su arreglo de puntuaciones $c$ no se barajarán durante todo el proceso, sino que únicamente se eliminarán sus prefijos.

Tanto Alice como Bob quieren maximizar sus puntuaciones. Alice quiere saber cuál es su puntuación esperada cuando ambos jugadores adoptan estrategias óptimas.

Alice también realizó $q$ grupos de modificaciones (modificando el arreglo y las puntuaciones), y quiere que encuentres la respuesta para el arreglo inicial, así como las respuestas después de cada grupo de modificaciones.

Entrada

La primera línea contiene un entero $n$ ($1 \le n \le 10^6$), que representa la longitud del arreglo inicial $a$.

La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), que representan el arreglo inicial $a$.

La tercera línea contiene $n$ enteros $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), que representan la puntuación de cada número en el arreglo.

La siguiente línea contiene un entero $q$ ($0 \le q \le 10$), que representa el número de grupos de modificaciones.

A continuación se describen los $q$ grupos de modificaciones:

Para cada grupo de modificaciones, la primera línea contiene $k_i$ ($1 \le k_i \le 10^5$), que indica el número de modificaciones en este grupo.

Las siguientes $k_i$ líneas contienen cada una tres enteros $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), indicando que $a_{p_j}$ se modifica a $x_j$ y $c_{p_j}$ se modifica a $y_j$.

Se garantiza que $p_1 < p_2 < \dots < p_{k_i}$.

Salida

Imprime un total de $q + 1$ líneas, cada línea con un número en punto flotante que representa la respuesta.

La primera línea es la respuesta para el arreglo inicial, seguida de $q$ líneas con las respuestas después de cada grupo de modificaciones.

Una respuesta se considera correcta si el error relativo o absoluto en comparación con la respuesta estándar no excede $10^{-9}$.

Ejemplos

Entrada 1

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

Salida 1

1.333333333333
3.000000000000
4.000000000000

Entrada 2

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

Salida 2

9.013888888889

Nota

Este problema tiene un tamaño de entrada grande; por favor utiliza un método de entrada eficiente.

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.