Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

Có một mảng $a$ độ dài $n$, trong đó số thứ $i$ là $a_i$. Ngoài ra, mỗi số có một điểm số, và điểm số của số thứ $i$ là $c_i$. Alice và Bob lần lượt chơi, với Alice đi trước.

Ở lượt hiện tại, người chơi trước tiên sao chép mảng $a$ sang mảng $b$ và chạy một chương trình xáo trộn ngẫu nhiên để xáo trộn ngẫu nhiên mảng $b$. Cụ thể, chương trình xáo trộn ngẫu nhiên sẽ chọn một trong các hoán vị của $b$ với xác suất bằng nhau và thay thế mảng $b$ ban đầu bằng hoán vị đó. Giả sử độ dài hiện tại của mảng $a$ là $m$, khi đó người chơi có thể chọn một số nguyên $k$ sao cho $0 \le k \le m$ và $a[1 \dots k] = b[1 \dots k]$, sau đó xóa $a[1 \dots k]$ (tức là tiền tố độ dài $k$ của $a$) và nhận được điểm số của các số bị xóa. Trò chơi kết thúc khi mảng $a$ trở nên rỗng.

Lưu ý rằng mảng $a$ và mảng điểm số $c$ của nó sẽ không bị xáo trộn trong suốt toàn bộ quá trình, mà chỉ có các tiền tố của chúng bị loại bỏ.

Cả Alice và Bob đều muốn tối đa hóa điểm số của mình. Alice muốn biết điểm số kỳ vọng của cô ấy là bao nhiêu khi cả hai người chơi đều áp dụng chiến lược tối ưu.

Alice cũng đã thực hiện $q$ nhóm chỉnh sửa (chỉnh sửa mảng và điểm số), và cô ấy muốn bạn tìm đáp án cho mảng ban đầu, cũng như đáp án sau mỗi nhóm chỉnh sửa.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 10^6$), biểu thị độ dài của mảng $a$ ban đầu.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), biểu thị mảng $a$ ban đầu.

Dòng thứ ba chứa $n$ số nguyên $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), biểu thị điểm số của mỗi số trong mảng.

Dòng tiếp theo chứa một số nguyên $q$ ($0 \le q \le 10$), biểu thị số nhóm chỉnh sửa.

Phần tiếp theo mô tả $q$ nhóm chỉnh sửa:

Đối với mỗi nhóm chỉnh sửa, dòng đầu tiên chứa $k_i$ ($1 \le k_i \le 10^5$), cho biết số lượng chỉnh sửa trong nhóm này.

$k_i$ dòng tiếp theo mỗi dòng chứa ba số nguyên $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), cho biết $a_{p_j}$ được sửa thành $x_j$ và $c_{p_j}$ được sửa thành $y_j$.

Đảm bảo rằng $p_1 < p_2 < \dots < p_{k_i}$.

Dữ liệu ra

In ra tổng cộng $q + 1$ dòng, mỗi dòng chứa một số thực dấu phẩy động biểu thị đáp án.

Dòng đầu tiên là đáp án cho mảng ban đầu, theo sau là $q$ dòng cho đáp án sau mỗi nhóm chỉnh sửa.

Một đáp án được coi là đúng nếu sai số tương đối hoặc tuyệt đối so với đáp án chuẩn không vượt quá $10^{-9}$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1.333333333333
3.000000000000
4.000000000000

Dữ liệu vào 2

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

Dữ liệu ra 2

9.013888888889

Ghi chú

Bài toán này có kích thước dữ liệu vào lớn, vui lòng sử dụng phương pháp nhập dữ liệu hiệu quả.

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.