Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

ישנו מערך $a$ באורך $n$, שבו המספר ה-$i$ הוא $a_i$. בנוסף, לכל מספר יש ניקוד, והניקוד של המספר ה-$i$ הוא $c_i$. Alice ו-Bob משחקים בתורות, כאשר Alice מתחילה ראשונה.

בסיבוב הנוכחי, השחקן מעתיק תחילה את המערך $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$ לא יעורבבו לאורך כל התהליך, אלא רק הרישות שלהם יוסרו.

גם Alice וגם Bob רוצים למקסם את הניקוד שלהם. Alice רוצה לדעת מהי תוחלת הניקוד שלה כאשר שני השחקנים נוקטים באסטרטגיות אופטימליות.

Alice גם ביצעה $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.