問題文
サヤさんはArcaeaを遊んでいます。また、ラクリミラさんはArcaeaの世界を変えることができる能力を持っています。
Arcaeaには譜面がN個存在し、譜面ごとに「譜面定数」が与えられています。
プレイヤーのランクを表す「ポテンシャル」は、次の手順で計算されます。
まず、1回のプレイで得られる「譜面ポテンシャル」は、次の式で決まります。
譜面ポテンシャル=譜面定数+そのプレイの補正スコア
同じ譜面を何度も遊んだ場合は、その譜面で得た譜面ポテンシャルの最大値をその譜面の記録として使います。
また、譜面定数が変更された場合は、過去のプレイの譜面ポテンシャルも変更されます。
プレイヤーのポテンシャルの計算方法は、順位と倍率の組を並べた倍率表T=((r1,w1),(r2,w2),…,(rk,wk))を用いて、次の手順で行います:
- 譜面ポテンシャルの上位rk譜面を大きい順に並べる。ただし、足りない分は譜面ポテンシャル0の記録で埋める。
- 1位からr1位までの譜面ポテンシャルに倍率w1を、r1+1位からr2位までの譜面ポテンシャルに倍率w2を、…、rk−1+1位からrk位までの譜面ポテンシャルに倍率wkを適用する。
- すべての倍率を適用した後、譜面ポテンシャルの加重平均(倍率をかけた譜面ポテンシャルの合計を倍率の合計で割った値)を計算する。
例えば、T=((1,3),(3,2),(5,1))で、上位5譜面の記録が(14,13,12,11,0)のとき、ポテンシャルは次の値です。
3+2+2+1+114×3+13×2+12×2+11×1+0×1=9103=11.444⋯
N個の譜面の譜面定数C1,C2,…,CNと、Q個のクエリが与えられます。
譜面1の譜面定数はC1、譜面2の譜面定数はC2、…、譜面Nの譜面定数はCNです。
クエリは以下の3種類のいずれかです:
- タイプ1:1spという形式で与えられます。サヤさんは譜面sを遊び、譜面ポテンシャルpを得ます。
- タイプ2:2scという形式で与えられます。ラクリミラさんは譜面sの譜面定数をcに変更します。
- タイプ3:3kr1w1⋯rkwkという形式で与えられます。ラクリミラさんは倍率表をT=((r1,w1),…,(rk,wk))に変更します。
各クエリ後、サヤさんの現在のポテンシャルを出力してください。
最初の状態ではサヤさんはまだ譜面を遊んでおらず、T=((10,2),(50,1))に設定されています。
制約
- Ci、p、cは小数点以下4桁までの小数で与えられる。
- それ以外の値は整数として与えられる。
- 1≤N≤105
- 1≤Q≤105
- 1.0000≤Ci≤12.0000
- タイプ1、2のクエリにおいて、1≤s≤N
- タイプ1のクエリにおいて、現在の譜面定数Csに対して、Cs≤p≤Cs+2.0000
- タイプ2のクエリにおいて、1.0000≤c≤12.0000
- タイプ3のクエリにおいて、1≤k≤105
- タイプ3のクエリにおいて、1≤r1<r2<…<rk≤N
- タイプ3のクエリにおいて、105≥w1>w2>…>wk≥1
- t番目のクエリを処理した直後の倍率表Tの長さをktとすると、∑t=1Qkt≤3×105
入力
入力は以下の形式で標準入力から与えられます。
ここでqueryiはi番目のクエリを表し、以下のいずれかの形式になります。
出力
Q行出力してください。
i行目には、i番目のクエリの後のサヤさんのポテンシャルを出力してください。
値の絶対誤差あるいは相対誤差が10−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
各クエリ後の記録と計算は次のとおりです。記録は譜面番号順に示し、未プレイの譜面は0と表記します。
| クエリ |
譜面ごとの記録 |
ポテンシャルの計算 |
| 1 |
(13,0,0) |
13×2/60 |
| 2 |
(13,12.9,0) |
(13×2+12.9×2)/60 |
| 3 |
(13,12.9,13.5) |
(13.5×2+13×2+12.9×2)/60 |
| 4 |
(13,12.9,13.5) |
(13.5×3+13+12.9)/5 |
| 5 |
(12.8,12.9,13.5) |
(13.5×3+12.9+12.8)/5 |
| 6 |
(12.9,12.9,13.5) |
(13.5×3+12.9+12.9)/5 |
| 7 |
(12.9,12.9,13.5) |
(13.5×3+12.9+12.9)/5 |
| 8 |
(12.9,12.9,13.5) |
(13.5+12.9)/2 |
クエリ4でT=((1,3),(3,1))となるため、1位だけに倍率3を適用します。クエリ7では、得られた譜面ポテンシャルがその譜面の記録を上回らないため、記録は変わりません。クエリ8ではT=((2,1))となり、上位2譜面の平均を求めます。
なお、rkはNより大きい可能性があることに注意してください。
サンプル 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
クエリ1では未プレイの譜面の譜面定数を変更するため、記録は0のままです。
クエリ2でT=((1,5),(2,2),(3,1))となります。1位、2位、3位の倍率は、それぞれ5,2,1です。
クエリ3の後の記録は(13.1,0,0)なので、ポテンシャルは13.1×5/(5+2+1)=8.1875です。クエリ4では記録が更新されません。
クエリ5では上位2譜面の平均に変更され、ポテンシャルは13.1/2=6.55です。クエリ6では譜面1の記録も0.2下がるため、ポテンシャルは12.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
クエリ1でT=((1,2),(2,1))となり、1位には倍率2、2位には倍率1を適用します。
クエリ2の後は13.1×2/3、クエリ3の後は(13.1×2+13.1)/3=13.1です。同じ記録の譜面が複数あっても、それぞれ別の順位として数えます。クエリ4で得られる記録13は上位2譜面に入らないため、ポテンシャルは変わりません。
クエリ5では譜面3が1位になり、ポテンシャルは(14×2+13.1)/3=13.7です。
クエリ6でT=((2,3),(3,1))となり、ポテンシャルは(14×3+13.1×3+13.1)/7=13.485714…です。クエリ7では1位の記録だけを使うため、ポテンシャルは14になります。