Let us denote by \(S[L:R]\) the substring of \(S\) consisting of its \(L\)-th through \(R\)-th characters.

String \(S[L:R]\) is a substring of \(T\) that is obtained by sorting \(S\) if and only if the following two conditions are met:

• \(S[L:R]\) are in ascending order of characters;
• let \(c\) be the minimum character contained in \(S[L:R]\), and \(d\) be the maximum, then every character between \(c\) and \(d\), exclusive, occurs the same times as in \(S\).

These can be determined by the number of occurrences of each character in a segment of \(S\). Thus, the problem can be solved in a total of \(O(\sigma(N+Q\log N))\) time with a segment tree for each character that manage the occurrence of the character.

Writer’s solution (C++)