Range Sort Query

セグメント木にマージソートを載せると、構築 $\Theta (NlogN)$、クエリ $\Theta (N)$ で処理できます。全体の計算量は $\Theta (N(logN + Q))$ です。

$\dots$ のはずが、想定より愚直解のほうが速いらしいです。

いろんな解き方がありそうなので verify とかに使ってね☆