概要
実装が易しめの平方分割解。あまり他の提出になさそうだったので一応書きます。
解法
列の平方分割により解きます。
数列 $A$ を、長さ $s$ の区間に区切ることにします。$n = \lceil N/s\rceil$ 個の区間に区切ります。各区間に対して、
- その区間内の要素をすべてソートして得られる列
- その列の累積和
を管理することにします。以下、クエリ処理について述べます。
変更クエリについては、変更した要素の属するバケットの情報を新しく作り直します。これは $O(s\log s)$ 時間で行えます。なお、ソート前後のインデックスの対応も管理しておけば、ここでのソートは $O(s)$ 時間でできます（変更した 1 要素を、左右にスワップしていけばよいです）。私の実装は $O(s\log s)$ 時間です。
中央値クエリは、二分探索により、$[L,R)$ 内の $x$ 以下の要素の個数や和を求める問題に帰着します。完全に $[L,R)$ に含まれている区間についてはソート列に対する二分探索を用いることで、二分探索の判定問題が $O(s + n\log s)$ 時間で解けます。
結局、クエリあたり $O(s\log s + (s + n\log n)\log A)$ 時間で解けることが分かりました。
$(s,n) = (\sqrt{N\log A}, \sqrt{N/\log A})$ 程度にとれば、この計算量は $O(\sqrt{N\log A}\log N)$ 程度になります。あまり余裕はありませんが、これで AC することができます。
なお、二分探索の $40$ 回のループを、これまで $A_i$ として現れたことのある $\log_2(N+Q)$ ループに削減することで、さらなる高速化が期待できます。
