Irreducible Anagrams
Contest: Codeforces Round 616 (Div. 1)
Difficulty rating: 1800
Tags: binary search, constructive algorithms, data structures, strings, two pointers

Let's call two strings $$$s$$$ and $$$t$$$ anagrams of each other if it is possible to rearrange symbols in the string $$$s$$$ to get a string, equal to $$$t$$$.

Let's consider two strings $$$s$$$ and $$$t$$$ which are anagrams of each other. We say that $$$t$$$ is a reducible anagram of $$$s$$$ if there exists an integer $$$k \ge 2$$$ and $$$2k$$$ non-empty strings $$$s_1, t_1, s_2, t_2, \dots, s_k, t_k$$$ that satisfy the following conditions:

1. If we write the strings $$$s_1, s_2, \dots, s_k$$$ in order, the resulting string will be equal to $$$s$$$;
2. If we write the strings $$$t_1, t_2, \dots, t_k$$$ in order, the resulting string will be equal to $$$t$$$;
3. For all integers $$$i$$$ between $$$1$$$ and $$$k$$$ inclusive, $$$s_i$$$ and $$$t_i$$$ are anagrams of each other.

If such strings don't exist, then $$$t$$$ is said to be an irreducible anagram of $$$s$$$. Note that these notions are only defined when $$$s$$$ and $$$t$$$ are anagrams of each other.

For example, consider the string $$$s = $$$ "gamegame". Then the string $$$t = $$$ "megamage" is a reducible anagram of $$$s$$$, we may choose for example $$$s_1 = $$$ "game", $$$s_2 = $$$ "gam", $$$s_3 = $$$ "e" and $$$t_1 = $$$ "mega", $$$t_2 = $$$ "mag", $$$t_3 = $$$ "e":

On the other hand, we can prove that $$$t = $$$ "memegaga" is an irreducible anagram of $$$s$$$.

You will be given a string $$$s$$$ and $$$q$$$ queries, represented by two integers $$$1 \le l \le r \le |s|$$$ (where $$$|s|$$$ is equal to the length of the string $$$s$$$). For each query, you should find if the substring of $$$s$$$ formed by characters from the $$$l$$$-th to the $$$r$$$-th has at least one irreducible anagram.

Input format:
The first line contains a string $$$s$$$, consisting of lowercase English characters ($$$1 \le |s| \le 2 \cdot 10^5$$$).

The second line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$)  — the number of queries.

Each of the following $$$q$$$ lines contain two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le |s|$$$), representing a query for the substring of $$$s$$$ formed by characters from the $$$l$$$-th to the $$$r$$$-th.

Output format:
For each query, print a single line containing "Yes" (without quotes) if the corresponding substring has at least one irreducible anagram, and a single line containing "No" (without quotes) otherwise.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, in the first and third queries, the substring is "a", which has itself as an irreducible anagram since two or more non-empty strings cannot be put together to obtain "a". On the other hand, in the second query, the substring is "aaa", which has no irreducible anagrams: its only anagram is itself, and we may choose $$$s_1 = $$$ "a", $$$s_2 = $$$ "aa", $$$t_1 = $$$ "a", $$$t_2 = $$$ "aa" to show that it is a reducible anagram.

In the second query of the second sample, the substring is "abb", which has, for example, "bba" as an irreducible anagram.

Example input:
aaaaa
3
1 1
2 4
5 5

Example output:
Yes
No
Yes

Example input:
aabbbbbbc
6
1 2
2 4
2 2
1 9
5 7
3 5

Example output:
No
Yes
Yes
Yes
No
No

Editorial:
We claim that a string has at least one irreducible anagram if and only if one of the following conditions holds:
• Its length is equal to $$$1$$$.
• Its first and last characters are different.
• It contains at least three different characters.
Once we have proven this characterization it is easy to solve the problem: For any given query, the first and second conditions are trivial to check, while the third condition can be checked efficiently if we maintain the number of appearances of each character in each prefix of our string. This allows us to answer queries in $$$O(k)$$$ where $$$k = 26$$$ is the size of our alphabet.
Now let's prove the characterization. Consider any string $$$s$$$ with $$$n = |s| \ge 2$$$. First note that for any two strings $$$a$$$ and $$$b$$$ that are anagrams, it is enough to check that no two proper prefixes of them are anagrams for them to be irreducible anagrams, because if $$$a$$$ and $$$b$$$ are reducible then $$$a_1$$$ and $$$b_1$$$ are two proper prefixes that are anagrams. We will consider three cases. In what follows all indices are $$$1$$$-based.
• If $$$s[1] \neq s[n]$$$.Write all occurrences of $$$s[n]$$$ in $$$s$$$, and then write all the remaining characters of $$$s$$$ in any order. Every proper prefix of the resulting string will have more occurrences of $$$s[n]$$$ than the corresponding prefix of $$$s$$$, so no two of them will be anagrams.
• If $$$s[1] = s[n]$$$ and $$$s$$$ has at least three different characters.Consider the last distinct character that appears in $$$s$$$. Write all occurrences of it, followed by all occurrences of $$$s[n]$$$, and then write the remaining characters of $$$s$$$ in any order. We can check that every proper prefix of the resulting strings contains more occurrences of either this last distinct character, or more occurrences of $$$s[n]$$$, than the corresponding prefix of $$$s$$$, so no two proper prefixes are anagrams.
• If $$$s[1] = s[n]$$$ and $$$s$$$ has at most two different characters.Assume that $$$s$$$ only has characters $$$a$$$ and $$$b$$$, and that $$$s[1] = a$$$. Assume that $$$s$$$ has an irreducible anagram $$$t$$$. Then $$$t[1] = b$$$, as otherwise $$$s[1, 1]$$$ and $$$t[1, 1]$$$ are anagrams.Consider the leftmost position $$$x$$$ such that the prefix $$$s[1, x]$$$ has at least as many appearances of $$$b$$$ as $$$t$$$. We have $$$x \le n - 1$$$ because $$$s[1, n - 1]$$$ contains every possible appearance of $$$b$$$. Moreover, we have $$$x > 1$$$. Now, notice that $$$t[1, x - 1]$$$ must have strictly more appearances of $$$b$$$ than $$$s[1, x - 1]$$$. This is only possible if this prefix had exactly one more appearance of $$$b$$$, and then $$$s[1, x]$$$ and $$$t[1, x]$$$ have the same number of appearances of $$$b$$$. But this means that the proper prefixes $$$s[1, x]$$$ and $$$t[1, x]$$$ are anagrams  — a contradiction.