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

Il y a un tableau $a$ de longueur $n$, où le $i$-ème nombre est $a_i$. De plus, chaque nombre a un score, et le score du $i$-ème nombre est $c_i$. Alice et Bob jouent à tour de rôle, Alice commençant en premier.

Au tour actuel, le joueur copie d'abord le tableau $a$ dans le tableau $b$ et exécute un programme de mélange aléatoire pour mélanger aléatoirement le tableau $b$. Plus précisément, le programme de mélange aléatoire sélectionne l'une des permutations de $b$ de manière équiprobable et remplace le tableau $b$ d'origine par celle-ci. Supposons que la longueur actuelle du tableau $a$ soit $m$ ; le joueur peut alors choisir un entier $k$ tel que $0 \le k \le m$ et $a[1 \dots k] = b[1 \dots k]$, puis supprimer $a[1 \dots k]$ (c'est-à-dire le préfixe de longueur $k$ de $a$) et obtenir le score des nombres supprimés. Le jeu se termine lorsque le tableau $a$ est vide.

Notez que le tableau $a$ et son tableau de scores $c$ ne seront pas mélangés tout au long du processus, seuls leurs préfixes seront supprimés.

Alice et Bob veulent tous deux maximiser leur score. Alice veut savoir quelle est son espérance de score lorsque les deux joueurs adoptent des stratégies optimales.

Alice a également effectué $q$ groupes de modifications (modifiant le tableau et les scores), et elle souhaite que vous trouviez la réponse pour le tableau initial, ainsi que les réponses après chaque groupe de modifications.

Entrée

La première ligne contient un entier $n$ ($1 \le n \le 10^6$), représentant la longueur du tableau initial $a$.

La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), représentant le tableau initial $a$.

La troisième ligne contient $n$ entiers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), représentant le score de chaque nombre dans le tableau.

La ligne suivante contient un entier $q$ ($0 \le q \le 10$), représentant le nombre de groupes de modifications.

Ce qui suit décrit les $q$ groupes de modifications :

Pour chaque groupe de modifications, la première ligne contient $k_i$ ($1 \le k_i \le 10^5$), indiquant le nombre de modifications dans ce groupe.

Les $k_i$ lignes suivantes contiennent chacune trois entiers $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), indiquant que $a_{p_j}$ est modifié en $x_j$ et $c_{p_j}$ est modifié en $y_j$.

Il est garanti que $p_1 < p_2 < \dots < p_{k_i}$.

Sortie

Affichez un total de $q + 1$ lignes, chaque ligne contenant un nombre à virgule flottante représentant la réponse.

La première ligne est la réponse pour le tableau initial, suivie de $q$ lignes pour les réponses après chaque groupe de modifications.

Une réponse est considérée comme correcte si l'erreur relative ou absolue par rapport à la réponse de référence ne dépasse pas $10^{-9}$.

Exemples

Entrée 1

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

Sortie 1

1.333333333333
3.000000000000
4.000000000000

Entrée 2

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

Sortie 2

9.013888888889

Remarque

Ce problème a une grande taille d'entrée, veuillez utiliser une méthode de lecture rapide.

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.