外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

H - Potential and World Changer

作成者 sevenc_nanashi

テスター unbakedbread

配点 500 点

実行時間制限
3 秒
メモリ制限
512 MiB

問題文

サヤさんはArcaeaを遊んでいます。また、ラクリミラさんはArcaeaの世界を変えることができる能力を持っています。
Arcaeaには譜面がNN個存在し、譜面ごとに「譜面定数」が与えられています。
プレイヤーのランクを表す「ポテンシャル」は、次の手順で計算されます。

まず、1回のプレイで得られる「譜面ポテンシャル」は、次の式で決まります。

譜面ポテンシャル=譜面定数+そのプレイの補正スコア\text{譜面ポテンシャル} = \text{譜面定数} + \text{そのプレイの補正スコア}

同じ譜面を何度も遊んだ場合は、その譜面で得た譜面ポテンシャルの最大値をその譜面の記録として使います。
また、譜面定数が変更された場合は、過去のプレイの譜面ポテンシャルも変更されます。

プレイヤーのポテンシャルの計算方法は、順位と倍率の組を並べた倍率表T=((r1,w1),(r2,w2),…,(rk,wk))T = ((r_1, w_1), (r_2, w_2), \ldots, (r_k, w_k))を用いて、次の手順で行います:

  • 譜面ポテンシャルの上位rkr_k譜面を大きい順に並べる。ただし、足りない分は譜面ポテンシャル00の記録で埋める。
  • 11位からr1r_1位までの譜面ポテンシャルに倍率w1w_1を、r1+1r_1+1位からr2r_2位までの譜面ポテンシャルに倍率w2w_2を、…\ldots、rk−1+1r_{k-1}+1位からrkr_k位までの譜面ポテンシャルに倍率wkw_kを適用する。
  • すべての倍率を適用した後、譜面ポテンシャルの加重平均(倍率をかけた譜面ポテンシャルの合計を倍率の合計で割った値)を計算する。

例えば、T=((1,3),(3,2),(5,1))T = ((1, 3), (3, 2), (5, 1))で、上位55譜面の記録が(14,13,12,11,0)(14, 13, 12, 11, 0)のとき、ポテンシャルは次の値です。

14×3+13×2+12×2+11×1+0×13+2+2+1+1=1039=11.444⋯\frac{14 \times 3 + 13 \times 2 + 12 \times 2 + 11 \times 1 + 0 \times 1}{3 + 2 + 2 + 1 + 1} = \frac{103}{9} = 11.444\cdots

NN個の譜面の譜面定数C1,C2,…,CNC_1, C_2, \ldots, C_Nと、QQ個のクエリが与えられます。
譜面11の譜面定数はC1C_1、譜面22の譜面定数はC2C_2、…\ldots、譜面NNの譜面定数はCNC_Nです。
クエリは以下の3種類のいずれかです:

  • タイプ11:1  s  p1 \; s \; pという形式で与えられます。サヤさんは譜面ssを遊び、譜面ポテンシャルppを得ます。
  • タイプ22:2  s  c2 \; s \; cという形式で与えられます。ラクリミラさんは譜面ssの譜面定数をccに変更します。
  • タイプ33:3  k  r1  w1  ⋯  rk  wk3 \; k \; r_1 \; w_1 \; \cdots \; r_k \; w_kという形式で与えられます。ラクリミラさんは倍率表をT=((r1,w1),…,(rk,wk))T=((r_1, w_1), \ldots, (r_k, w_k))に変更します。

各クエリ後、サヤさんの現在のポテンシャルを出力してください。
最初の状態ではサヤさんはまだ譜面を遊んでおらず、T=((10,2),(50,1))T = ((10, 2), (50, 1))に設定されています。

制約

  • CiC_i、pp、ccは小数点以下4桁までの小数で与えられる。
  • それ以外の値は整数として与えられる。
  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤Q≤1051 \leq Q \leq 10^5
  • 1.0000≤Ci≤12.00001.0000 \leq C_i \leq 12.0000
  • タイプ11、22のクエリにおいて、1≤s≤N1 \leq s \leq N
  • タイプ11のクエリにおいて、現在の譜面定数CsC_sに対して、Cs≤p≤Cs+2.0000C_s \leq p \leq C_s + 2.0000
  • タイプ22のクエリにおいて、1.0000≤c≤12.00001.0000 \leq c \leq 12.0000
  • タイプ33のクエリにおいて、1≤k≤1051 \leq k \leq 10^5
  • タイプ33のクエリにおいて、1≤r1<r2<…<rk≤N1 \leq r_1 < r_2 < \ldots < r_k \leq N
  • タイプ33のクエリにおいて、105≥w1>w2>…>wk≥110^5 \geq w_1 > w_2 > \ldots > w_k \geq 1
  • tt番目のクエリを処理した直後の倍率表TTの長さをktk_tとすると、∑t=1Qkt≤3×105\sum_{t=1}^{Q}k_t \leq 3 \times 10^5

入力

入力は以下の形式で標準入力から与えられます。

NN C1C2…CNC_1 \quad C_2 \quad \ldots \quad C_N QQ query1\text{query}_1 query2\text{query}_2 ⋮\vdots queryQ\text{query}_Q

ここでqueryi\text{query}_iはii番目のクエリを表し、以下のいずれかの形式になります。

1sp1 \quad s \quad p
2sc2 \quad s \quad c
3kr1w1…rkwk3 \quad k \quad r_1 \quad w_1 \quad \ldots \quad r_k \quad w_k

出力

QQ行出力してください。
ii行目には、ii番目のクエリの後のサヤさんのポテンシャルを出力してください。
値の絶対誤差あるいは相対誤差が10−610^{-6}以下であれば正解とみなされます。

サンプル 1

入力

3
11.3000 11.3000 12.0000
8
1 1 13.0000
1 2 12.9000
1 3 13.5000
3 2 1 3 3 1
2 1 11.1000
1 1 12.9000
1 2 12.8000
3 1 2 1

出力

0.4333333333333333
0.8633333333333334
1.3133333333333335
13.28
13.24
13.26
13.26
13.2

各クエリ後の記録と計算は次のとおりです。記録は譜面番号順に示し、未プレイの譜面は00と表記します。

クエリ 譜面ごとの記録 ポテンシャルの計算
1 (13,0,0)(13,0,0) 13×2/6013\times2/60
2 (13,12.9,0)(13,12.9,0) (13×2+12.9×2)/60(13\times2+12.9\times2)/60
3 (13,12.9,13.5)(13,12.9,13.5) (13.5×2+13×2+12.9×2)/60(13.5\times2+13\times2+12.9\times2)/60
4 (13,12.9,13.5)(13,12.9,13.5) (13.5×3+13+12.9)/5(13.5\times3+13+12.9)/5
5 (12.8,12.9,13.5)(12.8,12.9,13.5) (13.5×3+12.9+12.8)/5(13.5\times3+12.9+12.8)/5
6 (12.9,12.9,13.5)(12.9,12.9,13.5) (13.5×3+12.9+12.9)/5(13.5\times3+12.9+12.9)/5
7 (12.9,12.9,13.5)(12.9,12.9,13.5) (13.5×3+12.9+12.9)/5(13.5\times3+12.9+12.9)/5
8 (12.9,12.9,13.5)(12.9,12.9,13.5) (13.5+12.9)/2(13.5+12.9)/2

クエリ44でT=((1,3),(3,1))T=((1,3),(3,1))となるため、11位だけに倍率33を適用します。クエリ77では、得られた譜面ポテンシャルがその譜面の記録を上回らないため、記録は変わりません。クエリ88ではT=((2,1))T=((2,1))となり、上位22譜面の平均を求めます。

なお、rkr_kはNNより大きい可能性があることに注意してください。

サンプル 2

入力

3
11.2000 11.3000 12.0000
6
2 1 11.3000
3 3 1 5 2 2 3 1
1 1 13.1000
1 1 13.0000
3 1 2 1
2 1 11.1000

出力

0.0
0.0
8.1875
8.1875
6.55
6.45

クエリ11では未プレイの譜面の譜面定数を変更するため、記録は00のままです。

クエリ22でT=((1,5),(2,2),(3,1))T=((1,5),(2,2),(3,1))となります。11位、22位、33位の倍率は、それぞれ5,2,15,2,1です。

クエリ33の後の記録は(13.1,0,0)(13.1,0,0)なので、ポテンシャルは13.1×5/(5+2+1)=8.187513.1\times5/(5+2+1)=8.1875です。クエリ44では記録が更新されません。

クエリ55では上位22譜面の平均に変更され、ポテンシャルは13.1/2=6.5513.1/2=6.55です。クエリ66では譜面11の記録も0.20.2下がるため、ポテンシャルは12.9/2=6.4512.9/2=6.45となります。

サンプル 3

入力

3
11.1000 11.1000 12.0000
7
3 2 1 2 2 1
1 1 13.1000
1 2 13.1000
1 3 13.0000
1 3 14.0000
3 2 2 3 3 1
3 1 1 1

出力

0.0
8.733333333333333
13.1
13.1
13.7
13.485714285714288
14.0

クエリ11でT=((1,2),(2,1))T=((1,2),(2,1))となり、11位には倍率22、22位には倍率11を適用します。

クエリ22の後は13.1×2/313.1\times2/3、クエリ33の後は(13.1×2+13.1)/3=13.1(13.1\times2+13.1)/3=13.1です。同じ記録の譜面が複数あっても、それぞれ別の順位として数えます。クエリ44で得られる記録1313は上位22譜面に入らないため、ポテンシャルは変わりません。

クエリ55では譜面33が11位になり、ポテンシャルは(14×2+13.1)/3=13.7(14\times2+13.1)/3=13.7です。

クエリ66でT=((2,3),(3,1))T=((2,3),(3,1))となり、ポテンシャルは(14×3+13.1×3+13.1)/7=13.485714…(14\times3+13.1\times3+13.1)/7=13.485714\ldotsです。クエリ77では11位の記録だけを使うため、ポテンシャルは1414になります。

誤差ジャッジ:絶対誤差または相対誤差が10-6以下なら正解です。

参加受付は終了しました。