Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Є масив $a$ довжини $n$, де $i$-те число дорівнює $a_i$. Крім того, кожне число має бали, і кількість балів $i$-го числа дорівнює $c_i$. Аліса та Боб ходять по черзі, першою ходить Аліса.

У поточному раунді гравець спочатку копіює масив $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]$ (тобто префікс довжини $k$ масиву $a$) та отримати бали видалених чисел. Гра закінчується, коли масив $a$ стає порожнім.

Зверніть увагу, що сам масив $a$ та масив його балів $c$ протягом усього процесу не перемішуються, а лише видаляються їхні префікси.

І Аліса, і Боб хочуть максимізувати свої бали. Аліса хоче дізнатися, яким є математичне сподівання її балів, якщо обидва гравці дотримуються оптимальних стратегій.

Аліса також зробила $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.