Array Transformer (UVa 12003 World Finals Warmup 2011 2)

長さnの数列Aと数値uが与えられる。次に[l,r]の範囲のv未満の数値の個数をkとした時に、a[p]をu*k/(r-l+1)にするクエリがm個来る。最終的な数列の値を答えよ。
1<=n<=300,000
1<=m<=50,000
1<=u<=1,000,000,000

数列を平方根分割して、それぞれのブロックに存在する数値をソートしてvectorに保存しておく。そうしておけば各クエリに対してkを数えるのは $O(\sqrt{n}\log n)$ で処理でき、値の更新も単純に前の値を消して、正しい場所に挿入すれば $O(\sqrt{n})$ で処理できる。