Universal Cup Judging System

Universal Cup

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

Terdapat sebuah larik $a$ dengan panjang $n$, di mana bilangan ke-$i$ adalah $a_i$. Selain itu, setiap bilangan memiliki skor, dan skor dari bilangan ke-$i$ adalah $c_i$. Alice dan Bob bermain secara bergiliran, dengan Alice melangkah lebih dulu.

Pada ronde saat ini, pemain pertama-tama menyalin larik $a$ ke larik $b$ dan menjalankan program pengacakan acak untuk mengacak larik $b$ secara acak. Secara spesifik, program pengacakan acak akan memilih salah satu permutasi dari $b$ dengan peluang yang sama dan menggantikan larik $b$ semula dengannya. Misalkan panjang larik $a$ saat ini adalah $m$, maka pemain dapat memilih sebuah bilangan bulat $k$ sedemikian sehingga $0 \le k \le m$ dan $a[1 \dots k] = b[1 \dots k]$, lalu menghapus $a[1 \dots k]$ (yaitu prefiks sepanjang $k$ dari $a$) dan memperoleh skor dari bilangan-bilangan yang dihapus. Permainan berakhir ketika larik $a$ menjadi kosong.

Perhatikan bahwa larik $a$ dan larik skornya $c$ tidak akan diacak sepanjang seluruh proses, melainkan hanya prefiksnya saja yang dihapus.

Baik Alice maupun Bob ingin memaksimalkan skor mereka. Alice ingin mengetahui berapa nilai harapan skornya ketika kedua pemain menerapkan strategi optimal.

Alice juga melakukan $q$ kelompok modifikasi (memodifikasi larik dan skor), dan ia ingin Anda mencari jawaban untuk larik awal, serta jawaban setelah setiap kelompok modifikasi.

Masukan

Baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 10^6$), yang menyatakan panjang larik awal $a$.

Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), yang menyatakan larik awal $a$.

Baris ketiga berisi $n$ bilangan bulat $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), yang menyatakan skor dari setiap bilangan di dalam larik.

Baris berikutnya berisi sebuah bilangan bulat $q$ ($0 \le q \le 10$), yang menyatakan banyaknya kelompok modifikasi.

Bagian berikut mendeskripsikan $q$ kelompok modifikasi:

Untuk setiap kelompok modifikasi, baris pertama berisi $k_i$ ($1 \le k_i \le 10^5$), yang menyatakan banyaknya modifikasi dalam kelompok ini.

$k_i$ baris berikutnya masing-masing berisi tiga bilangan bulat $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), yang menyatakan bahwa $a_{p_j}$ diubah menjadi $x_j$ dan $c_{p_j}$ diubah menjadi $y_j$.

Dijamin bahwa $p_1 < p_2 < \dots < p_{k_i}$.

Keluaran

Keluarkan total $q + 1$ baris, masing-masing baris berisi sebuah bilangan titik-mengambang yang menyatakan jawabannya.

Baris pertama adalah jawaban untuk larik awal, diikuti oleh $q$ baris untuk jawaban setelah setiap kelompok modifikasi.

Jawaban dianggap benar jika galat relatif atau absolut dibandingkan dengan jawaban standar tidak melebihi $10^{-9}$.

Contoh

Masukan 1

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

Keluaran 1

1.333333333333
3.000000000000
4.000000000000

Masukan 2

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

Keluaran 2

9.013888888889

Catatan

Persoalan ini memiliki ukuran masukan yang besar, harap gunakan metode pembacaan masukan yang efisien.

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.