雑な記事です
do you know the problem …
お気持ち
ソートした部分を binary trie(補足1) で持っておけば、 split が $O(\log N)$ になるのでソートが償却できそうですね。以降、 trie といえば binary trie で話を進めます。
trie の列を管理します。各クエリの区間の境界を覆う trie はそこで分割しておきます。
point set は $1$ 要素の trie を更新するだけです。
range product は trie 全体の積をセグ木に乗せるとただのセグ木のクエリになります。
range sort はいくつかの trie を融合します。（なお、添え字の重複は除かれています。）融合中、両方の trie のノードが重なる場合はそのノードが消えるので、このコストをノード生成に押し付けると trie の融合のコストが償却 $O(1)$ 時間になります。
実装
いい感じに改造して最短実行時間を目指しましょう。そのためにとりあえず動くのを理解しましょう。
添え字 $p_i$ の範囲を $[0,V)$ 内の整数とします。
実装例 ： https://judge.yosupo.jp/submission/104127
要素
reverse する必要があります。私はモノイド HalfElem に対して、要素列の積とその逆順の積の組で Elem としました。(補足2)
trie の各ノードでは、その部分に含まれる要素数（ trie のサイズ ）を管理する必要があります。
trie
必要な機能は次の通りです。(補足3)
- $C$ = meld( $T_1$ , $T_2$ ) ： trie $T_1$ と $T_2$ を融合する。葉ノードは重複しない。
- $(C_L,C_R)$ = split( $T$ , $p$ ) ： trie $T$ を破壊して左から $p$ 要素とそれ以外に分ける。
- $C$ = new( $p$ , $a$ , $V$ ) ： HalfElem $a$ と添え字 $p$ をもつ $1$ 要素のみからなる trie $C$ を構築する。 trie を構築する際、添え字は $[0,V)$ を管理できるようにする。(補足4)
- $A$ = prod( $C$ ) ： trie $C$ の product を Elem の形で求める。
なお、 trie はポインタ木で構築するものとし、空の trie は nullptr で表すものとします。
new と prod は Elem を乗せた”動的セグ木”と同じなので特にいうことはないです。
meld と split は再帰関数で表せます。
$\hspace{0pt}\text{meld}( T_1 , T_2 )$
$\hspace{16pt}\text{if }T_1\text{ is null : return }T_2$
$\hspace{16pt}\text{if }T_2\text{ is null : return }T_1$
$\hspace{16pt}T_1\text{.children}[0]\leftarrow\text{meld}(T_1\text{.children}[0],T_2\text{.children}[0])$
$\hspace{16pt}T_1\text{.children}[1]\leftarrow\text{meld}(T_1\text{.children}[1],T_2\text{.children}[1])$
$\hspace{16pt}\text{delete }T_2$
$\hspace{16pt}\text{return }T_1$
$\hspace{0pt}\text{split}( T , p )$
$\hspace{16pt}\text{if }p=0\text{ : return }(\text{null},T)$
$\hspace{16pt}\text{if }p=|T|\text{ : return }(T,\text{null})$
$\hspace{16pt}\text{if }p\lt |T\text{.children}[0]|\text{ :}$
$\hspace{32pt}C_1,C_{2L}\leftarrow\text{split}( T\text{.children}[0] , p )$
$\hspace{32pt}C_2\leftarrow\text{a new node with children }(C_{2L},T\text{.children}[1])$
$\hspace{16pt}\text{else :}$
$\hspace{32pt}C_{1R},C_2\leftarrow\text{split}( T\text{.children}[1] , p-|T\text{.children}[0]| )$
$\hspace{32pt}C_1\leftarrow\text{a new node with children }(T\text{.children}[0],C_{1R})$
$\hspace{16pt}\text{return }(C_1,C_2)$
split のときの delete を考慮して書くと面倒なのでよしなにしてください。
trie の強化
trie の機能は作ったので、 $[0,V)$ を管理する trie を Tree でラッピングします。
私が実装するときには、 Tree では
- trie の根のポインタ
- 降順ソートのとき true になるフラグ
- trie の高さ
を管理しました。
trie の列から検索
trie の列から、操作対象の trie を検索します。
- $T$ = find( $p$ ) ： 要素列の $p$ 番目を管理に含めている trie を求める。
- split( $p$ ) ： 要素列の $p$ 番目の直前で trie が分割されている状態にする。
trie が管理する区間の右端を std::set に入れて、 trie 本体は std::vector<Tree> に入れれば処理できます。
また、右端を基準にして trie の product をセグメント木に乗せます。これらは適宜更新してください。
必要なクエリを実装
point set は両側で split して $1$ 点上書きするだけです。
range prod は両側で split するとセグメント木の range prod になります。
range sort は両側で split し、区間内の trie をすべてマージします。最後に昇順か降順かの設定をします。
補足
(補足1) binary じゃなくて 4-ary とかでも計算量解析は同様にできるんじゃないですか（自信なし）。 3-ary は遷移の計算がややこしそう。
(補足2) reverse 関数を定義してもよいでしょう。ただ、メリットを得るためには入力の時点で reverse できる形にする必要があって、あまりうれしくない気がします。
(補足3) ノードをすべて delete する、みたいな機能があるとよいかもしれません。メモリ確保して解放をさぼるのが楽ですが、メモリがかかるデータ構造なので気を付けておきたいところでもあります。
(補足4) 同じ $V$ に対して同じ配置を構築しなければなりません。 $k$ 進数から $k$-ary trie を作れば特に問題ありません。また、結局上位のデータ構造から管理されるので、 $V$ を毎回与えるのはあまり大変ではないです。