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.