数列 \( (q_1 ,q_2 ,q_3 ,…,q_N )\) を 公式解説 と同様に定めます。

数列 \( (q_1 ,q_2 ,q_3 ,…,q_N )\) を大きさ \(\lfloor\sqrt{N}\rfloor\) 毎のユニットに分けます。例えば、\(N = 9\) で数列 \( (q_1 ,q_2 ,q_3 ,…,q_9 )\) が

• \(-2, -1, 2, -3, 9, -1, -3, -3, -4\)

である場合、

• \([-2, -1, 2], [-3, 9, -1], [-3, -3, -4]\)

と大きさが 3 の 3 つのユニットに分けます。

次に、各ユニット毎に

• ユニット内の \(q_i\) の合計値 (\(t\))
• ユニット内でレーティング変動しなくなるために、ユニットの手前までに必要となる \(q_i\) の合計値 (\(u\))

を計算しておきます。上記の例だと、

• \(\{t = -1, u = 1\}, \{t = 5, u = -6\}, \{t = -10, u = 3\}\)

となります。

各クエリに対する処理としては、まず上記の \(t, u\) を更新することを考えます。クエリにより更新されるのは \(q_i\) の一箇所だけで、その一箇所が属するユニットの \(t, u\) だけを更新すればよいです。

次に全コンテスト参加後のレーティングを求めます。これは以下のアルゴリズムにより可能です。

1. \(total = 0\) とする。
2. 先頭のユニットから順番に以下の処理を行う
   • \(total < u\) なら、そのユニット内でレーティング更新が止まることはないため、 \(total\) に \(t\) を加算して次のユニットに進む
   • \(total >= u\) なら、そのユニット内でレーティング更新が止まるため、ユニット内の各 \(q_i\) を先頭から順番に \(total\) に足していく。\(total >= 0\) となった時点で、\(cnt = (全ユニットを通して処理した q_i の個数)\) とし、 \((total+ B*cnt) / cnt\) を出力して アルゴリズムを終了する。
3. 全てのユニットに対する処理が終了したら、\((total+ B*N) / N\) を出力してアルゴリズムを終了する。

例に対してアルゴリズムを適用すると以下のようになります。

• \(total = 0\) とする。
• 1つ目のユニットは \(u = 1\) で \(total < u\) なので、\(total\) に \(t = 1\) を足して \(total = 1\) となります。
• 2つ目のユニットは \(u = -6\) で \(total >= u\) なので、ユニット内の \(q_i\) を順番に足していきます。
  • \(total\) に \(-3\) を足して \(total = -4\) となります。\(total < 0\) なので次に進みます。
  • \(total\) に \(9\) を足して \(total = 5\) となります。 \(total >= 0\) となったので、答えを計算してクエリの処理を終了します。

クエリ処理開始前の入力等の処理に \(O(N+Q)\)、各クエリの処理に \(O(\sqrt{N})\) かかり、クエリが \(Q\) 個であるため、計算量は全体で \(O(N + Q\sqrt{N})\) となります。

実装例 : https://atcoder.jp/contests/abc292/submissions/39459458