Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

توجد مصفوفة $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.