yukicoder No.1471 Sort Queries - かんプリンの学習記録

Mo's algorithmを用いた方法を説明します．

問題概要

英小文字からなら長さ ${N}$ の文字列 ${S}$ について「 ${L_i}$ 文字目から ${R_i}$ 文字目までからなる部分文字列を任意に並べ替えたものの中で辞書順最小である文字列の ${X_i}$ 文字目を出力せよ」という ${Q}$ 個のクエリに答えよ．

${1\leq N,Q \leq 10^4}$

Mo's algorithmについては以下の記事を見てください．
kanpurin.hatenablog.com

今回の問題はこれを満たしているのでMo's algorithmが使える．

${[l,r)}$ の各文字の個数を持っておけばよい．区間の伸縮も ${O(1)}$ で計算できる．計算量はアルファベットサイズを ${\sigma}$ として ${O(N\sqrt{Q}+\sigma Q)}$

個数の保持にBITを用いれば， ${O((N\sqrt{Q}+Q)\log{\sigma}+\sigma)}$ となり， ${\sigma\leq 10^5}$ でも解ける．

Mo's algorithmの復習になる．