AtCoder日本語につき問題文は略。code-festival-2016-qualb.contest.atcoder.jp解法を2つ紹介する。遅い解法まず、与えられた文字列たちに対してtrieを構築する。trieを構築した図。各文字列の終端を示す頂点にマークを付けておき、各頂点には、「それ以下にある終端の数」を覚えさせておく。クエリが来るたびに、対象の文字列を使って木を辿る。各分岐で、「今見ている文字よりも小さい」枝の先以下にある数値を合計する。これが、自分よりも辞書順で小さい文字列の数となる。