Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

長さ $n$ の配列 $a$ があり、$i$ 番目の数は $a_i$ です。さらに、各数にはスコアがあり、$i$ 番目の数のスコアは $c_i$ です。Alice と Bob が交互に手番を行い、Alice が先手です。

現在のラウンドでは、手番のプレイヤーはまず配列 $a$ を配列 $b$ にコピーし、ランダムシャッフルプログラムを実行して配列 $b$ をランダムにシャッフルします。具体的には、ランダムシャッフルプログラムは $b$ の順列のうち $1$ つを等確率で選び、元の配列 $b$ をそれで置き換えます。現在の配列 $a$ の長さを $m$ とすると、プレイヤーは $0 \le k \le m$ かつ $a[1 \dots k] = b[1 \dots k]$ を満たす整数 $k$ を選び、$a[1 \dots k]$(すなわち $a$ の長さ $k$ の接頭辞)を削除して、削除された数のスコアを得ることができます。配列 $a$ が空になった時点でゲームは終了します。

なお、全体の過程を通して配列 $a$ とそのスコア配列 $c$ 自体はシャッフルされず、それらの接頭辞のみが削除されることに注意してください。

Alice と Bob はともに自身のスコアを最大化したいと考えています。Alice は、両プレイヤーが最適な戦略をとったときの彼女の期待スコアがいくらになるかを知りたいと思っています。

また、Alice は $q$ グループの更新(配列とスコアの変更)を行いました。彼女は初期配列に対する答えと、各グループの更新後の答えを求めてほしいと思っています。

入力

最初の行には、初期配列 $a$ の長さを表す整数 $n$ ($1 \le n \le 10^6$) が含まれます。

$2$ 行目には、初期配列 $a$ を表す $n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) が含まれます。

$3$ 行目には、配列内の各数のスコアを表す $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$ 行にはそれぞれ、$a_{p_j}$ を $x_j$ に変更し、$c_{p_j}$ を $y_j$ に変更することを表す $3$ つの整数 $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$) が含まれます。

$p_1 < p_2 < \dots < p_{k_i}$ が保証されます。

出力

合計 $q + 1$ 行を出力してください。各行には答えを表す浮動小数点数を $1$ つ出力します。

$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.