読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2326 Number Sorting

解法

制約を見ると,B-A \le 10^5 という怪しい制約があるので,D=B-Aとします.
まずこの時点で想定解法はO(D)O(D log D)とかその辺を疑います.(桁DPの可能性もありますがこの制約である必要があまりなさそうなので切り捨てました.)

小さい数字から追加して条件を満たす集合を作っていくことを考えると,新たに追加する数字は集合に入っているどの数字よりも辞書順で大きい数字になります.
この形は配るDPっぽい形なのですが実装がしづらいので,漸化式を立てて貰うDPにします.
集合のうち最も大きい数字がvである組み合わせをF(v)とし, \left[ A,B \right] のうちvが辞書順で何番目であるかをS(v)と表すと,

F(v)=1+\sum_{u < v \& \& S(u) < S(v) }F(u)
という漸化式が立てられます.
愚直にやるとO(D^2)ですが,辞書順にFの値を決定していくことを考え,未決定の値は0であるとしたとき,
F(v)=\sum_{i = A}^{v - 1} F(i)
というように連続した区間の値の合計値をとればいいことになります.
あとはBITで殴ればいいので,計算量はO(DlogBlogD)になるとおもいます.
辞書順のソートのところで,SA_ISを使って殴るとO(D(logN+logD)まで落ちそうな気がしますが,そこまでする必要はないと思います.

ソースコード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1942114#1
ソースコードではG( S(v))=F(v)となるGを値の昇順に求めています.
やってることはほぼ同じです.