解説
入力される譜面定数・譜面ポテンシャルは小数点以下4桁までなので、倍して整数として扱います。以下では、この整数に変換した値を使い、出力時にで割ることにします。
ポテンシャルの計算を高速に行うことを考えます。
倍率が同じ順位区間ごとに、譜面ポテンシャルの合計を求めます。とおくと、位から位までの倍率はです。
ここで、関数を考え、とします。位から位までの合計は、累積和の差で求められます。したがって、
と表せます。例えば、ならば、分子は、分母はです。の場合は、この式でとなります。
順位区間を順に処理し、直前のを保持しておけば、を回求めれば計算できます。記録がの順位も倍率の合計に含めるため、分母では譜面数をで打ち切らず、各区間の長さを使います。
では、関数を高速に計算するにはどうすればよいでしょうか。
譜面ポテンシャルの最大値が()であることを利用します。累積和Segment Treeを用いると、ある点以上のポテンシャルを持つ譜面の数や、ある点以上のポテンシャルを持つ譜面の合計ポテンシャルを高速に求めることができます。
よって、以下のように関数を作ることができます:
- Segment Tree上の二分探索で「ある点以上のポテンシャルを持つ譜面の数が以上になる点の中で最大のもの」を求めます。
- ただし、の場合は、とします。
- その点以上のポテンシャルを持つ譜面の合計ポテンシャルを求めます。
- ただし、同率で位の譜面が複数存在する場合、譜面数がを超えてしまうことがあるため、その分を引く必要があります。
譜面ポテンシャルごとの譜面の数とポテンシャルの合計をそれぞれSegment Treeで管理し、また譜面ごとの記録・譜面定数をそれぞれ配列で管理します。
- 初期状態では、全ての譜面のポテンシャルをとしてSegment Treeに登録します。
- タイプのクエリでは、譜面の記録が更新される場合に、譜面数・合計ポテンシャルのSegment Tree、および譜面ごとの記録を更新します。
- タイプのクエリでは、もし譜面をすでにプレイ済なら、記録にを加え、譜面数・合計ポテンシャルのSegment Tree、および譜面ごとの記録を更新します。また、プレイ済かどうかに関わらず、譜面の譜面定数を更新しておきます。
- タイプのクエリでは、倍率表を更新します。
ポテンシャルの最大値を、各クエリ後の倍率表の長さの合計をとすると、クエリ処理の計算量はとなります。制約よりなので、これは十分高速です。
なお、ACLのFenwick Treeを用いると計算量はとなり、一部の言語(特にJITがある場合)ではこちらのほうが高速になる場合があります。
Fenwick Treeでの実装例(Ruby、2076ms)
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。