◆ 変更クエリのない場合

数列 \(A = (A_1, \ldots, A_N)\) に対して、\(F(A) = \sum_{i < j} | A_i - A_j|\) と書くことにします。\(\lim_{n\to\infty} f(n) = F(A) / 2\) であることを示しましょう。

\(A_i < A_k < A_j\) となる \(k\) が存在しないような \((A_i, A_j)\) に対する操作を良い操作と呼ぶことにします。操作・良い操作に対して次を確かめることができます。

• \(x\) 点を獲得する操作に対して、\(F(A)\) の値は \(2x\) 以上減少する。
• \(x\) 点を獲得する良い操作に対して、\(F(A)\) の値はちょうど \(2x\) 減少する。

証明は容易なので省略します。

\(F(A)\) はその定義から、\(0\) 未満になることはありません。したがってまず、任意の \(n\) に対して \(2f(n) \leq F(A)\) が成り立つことが分かります。

\(\lim_{n\to\infty} f(n) = F(A) / 2\) を示すには、良い操作のみを繰り返すことで \(F(A)\) を限りなく \(0\) に近づけられることを示せばよいです。

必要であれば添字をつけなおして、\(A_1\leq A_2\leq\cdots\) を仮定しておきます。このとき簡単な計算により \(\forall i, |A_i - A_{i+1}| < C \implies F(A) < \frac{N(N-1)}{2}C\) が成り立つことが分かります。この対偶から、\(|A_i - A_{i+1}| \geq \frac{2F(A)}{N(N-1)}\) となる \(i\) の存在が分かります。特に、\(x = \frac{F(A)}{N(N-1)}\) として、良い操作を行うことが可能です。この操作の結果、\(F(A)\) の値はちょうど \(r = 1 - \frac{2}{N(N-1)}\) 倍に変化します。

このことを \(n\) 回繰り返すことで、\(n\) 回の良い操作により \(F(A)\) の値を \(r^n\) 倍にすることができます。\(0\leq r < 1\) なので、良い操作のみで \(F(A)\) を限りなく \(0\) に近づけられることが示されました。

◆ 答の計算・クエリ処理

数列 \(A\) について項の順序は問題と無関係であるため、\(A\) を多重集合と見なしておきます。

\(A\) に要素を追加・削除しながら、答の差分を計算していくことを考えます。適当な数 \(x\) に対して \(\sum_{a\in A} |x - a|\) が計算できればよいことが分かります。

これは、区間 \([0, x)\) および \([x, \infty)\) に含まれる \(a\in A\) の個数や和が取得できれば計算できます。これは例えば、座標圧縮した後で Fenwick 木 やセグメント木 を利用することで実現可能です。

なお、答の差分ではなく答そのものをセグメント木で計算することもできます。

◆ 解答例

• https://atcoder.jp/contests/arc126/submissions/25825782
• https://atcoder.jp/contests/arc126/submissions/25825497