この問題は、すなわち N 要素の整数配列 A について以下のクエリを実行せよという問題である。
小課題は 4 つあり、そのうち最も難しい小課題 4 では N ≦ 30 000 であるから 1 回のクエリにつき O(N) よりも短い時間でクエリを実行する必要がある。
この小課題では N ≦ 100 であるからクエリを単純に処理するプログラムによって 12 点を得ることができる。具体的には変更クエリに対して A[i] ← x を素直に実行し、質問クエリに対して実際に A[p..q] にバブルソートを行って交換回数を求めればよい。
この方法は変更クエリに O(1) 、質問クエリに O(N^2) の時間を要するので全体では O(P + Q N2) 時間で動作する。
ある数列をバブルソートする際の交換回数は実際にバブルソートをするよりも効率よく計算することができる。ある数 x に注目したとき、x が交換される回数は x よりも数列の前のほうに出現し、かつ x よりも大きい数の個数に等しい。この問題では 1 ≦ A[i] ≦ N であるから、BIT(Binary Indexed Tree) などのデータ構造を使って数の出現頻度を管理することで質問クエリを O(N log N) で処理することが可能になる。これを実装すれば 30 点を得ることができる。
なおこの方法では変更クエリは単純な O(1) のままでよいので、全体では O(P + Q N log N) 時間で動作する。
この 2 つの小課題は前 2 つの小課題に比べて非常に解くのが難しいので、まず P = 0、 すなわち変更クエリがこない場合について効率よく質問クエリを処理することを考える。
そのためには平方分割を使う。まず √N 個のバケットを用意し、各バケットに √N 個ずつ要素を順番に入れる。こうしてできたバケットのうち i 番目を B[i] と書くことにする。
質問クエリを高速に処理するためには前処理が必要である。すべての i, j (0 ≦ i ≦ j < √N) についてバケット B[i] から B[j] までの (j-i+1)√N 個の要素をバブルソートする際の交換回数 S[i][j] をプロシージャ init 中で求めておく。これは i を固定して j を小さい方から動かしていき、小課題 2 の方法で交換回数を求めていくことで各 i について O(N log N) 時間で S[i][j] をすべての j について計算できるので、全体で O(N √N log N) 時間で行える。
さらにもうひとつの前処理が必要となる。すべての i (0 ≦ i < √N) について、バケット B[0] から B[i] までの (i+1)√N 個の要素の中での数の出現頻度 F[i][x] をプロシージャ init 中で求めておく。すなわち F[i][x] は B[0] から B[i] までの要素のうち x の出現個数である。後に F[i] 中の連続した範囲の和を計算する必要があるので各 F[i] は BIT で実現する。F[i] はこれも A の要素を順番に見ていき、各バケットの境目ごとに数の出現頻度を記憶していくことで効率よく計算できる。この部分には O(N √N + N log N) の時間がかかる。
この S, F を用いて質問クエリを高速に処理することができる。まず、パラメータ p, q に対して、A[p], A[q] の属するバケットをそれぞれ B[u], B[v] とする。そして A[p..q] を3つの範囲に分割して考える。すなわち B[u..v] に含まれる部分と、B[u..v] よりも前のほうにある部分(L とおく)と、B[u..v] よりも後のほうにある部分(R とおく)である。ここで各バケットのサイズは √N なので、B[u..v] に含まれない部分の要素の個数は高々 2√N となることが重要である。
3つの部分のうち B[u..v] に含まれる部分を先に考える。 B[u..v] だけをバブルソートするのに必要な交換回数はすでに計算済みで S[u][v] を参照するだけで求めることができるので、これをまず答に加える。これは明らかに O(1) 時間で済む。次に B[u..v] と L について考える。L の各要素 x に対して「B[P..Q] 中にあり、かつ x よりも小さいものの個数」を求めれば B[u..v] と L をバブルソートするのに必要な交換回数が求まる。この個数を求める際に数の出現頻度 F を用いる。R についても同様に、各要素 y に対して「B[u..v] の中にあり、かつ y よりも大きいものの個数」を求めればよい。L, R の要素数がそれぞれ √N 以下であるから、この計算には O(√N log N) の時間がかかる。
最後に L と R をバブルソートすることを考えると、これは L と R をこの順に連結した数列をバブルソートする際の交換回数を求めるだけでよい。|L|+|R| ≦ 2√N であるからこの計算も O(√N log N) で済むので、以上から質問クエリに O(√N log N) で答えることが可能である。ここまでを実装すれば 60 点が得られる。
P ≠ 0 の場合でも基本的な考え方は P = 0 のときと変わらない。まず平方分割を行い、質問クエリに答えるために前もって計算した S, F を使うところは同じである。
値の変更クエリによって問題になるのは、前もって計算した S, F の値を変更しなければならないということである。このうち F は √N 個以下のBITを更新するだけでよいので単純に O(√N log N) 時間で変更することができる。S はぜんぶで O(N) 個の値を持っているので、これを単純に更新すると時間がかかりすぎる。
ある値を変更したときに S の値がどのように変化するか考えよう。変更される値を A[i] として、変更後の値を x とする。このとき A[i] よりも前にある数 y について考える。y と A[i] の両方を含むような区間をバブルソートする際の交換回数が変化するのは、x < y ≦ A[i] または A[i] < y ≦ x が成り立つような場合である。前者の場合交換回数は 1 だけ増え、後者の場合は 1 だけ減る。A[i] よりも後にある数についても同様に考えることが出来るので、ここでは A[i] よりも前にある数についてだけ考える。さらに x < y ≦ A[i] の場合と A[i] < y ≦ x の場合も同じ考え方で増減を逆にするだけなので x < y ≦ A[i] となるようなものについてのみ考える。
まず A[i] が属するバケットを B[u] とする。 B[u] 内にあり、A[i] よりも前にある数のうち x < y ≦ A[i] を満たすような y の個数を数える。この個数を m とすると、すべての v (u ≦ v) について S[u][v] の値が m だけ増加する。さらに w (w < u) なるバケット B[w] について B[w..u-1] 中にある数のうち x < y ≦ A[i] を満たすような y の個数を数える。これは F を使うことで O(log N) 時間で計算できる。この個数を k とすると、すべての v (u ≦ v) について S[w][v] の値が m+k だけ増加する。ここで各 S[w] を BIT や segment tree などのデータ構造でもっておくと、ある範囲に同じ数を加算する操作が O(log N) で行えるので、すべての w についてこの更新を行うことで O(√N \log N) 時間で S の更新を完了できる。
以上から、1回の変更クエリと質問クエリにそれぞれ O(√N log N) 時間かかるアルゴリズムが得られる。さらに最初の前処理にかかる時間 O(N √N log N) を考慮して、全体では O((N+P+Q) √N log N) で動作する。これは小課題 4 を解くのに十分であり、100 点が得られる。