CF1290B.Irreducible Anagrams
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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≥2 and 2k non-empty strings s1,t1,s2,t2,…,sk,tk that satisfy the following conditions:
- If we write the strings s1,s2,…,sk in order, the resulting string will be equal to s ;
- If we write the strings t1,t2,…,tk in order, the resulting string will be equal to t ;
- For all integers i between 1 and k inclusive, si and ti 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≤l≤r≤∣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.
输入格式
The first line contains a string s , consisting of lowercase English characters ( 1≤∣s∣≤2⋅105 ).
The second line contains a single integer q ( 1≤q≤105 ) — the number of queries.
Each of the following q lines contain two integers l and r ( 1≤l≤r≤∣s∣ ), representing a query for the substring of s formed by characters from the l -th to the r -th.
输出格式
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.
输入输出样例
输入#1
aaaaa 3 1 1 2 4 5 5
输出#1
Yes No Yes
输入#2
aabbbbbbc 6 1 2 2 4 2 2 1 9 5 7 3 5
输出#2
No Yes Yes Yes No No
说明/提示
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.