307029: CF1290B. Irreducible Anagrams
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Irreducible Anagrams
题意翻译
定义两个长度相同的串 s,t 为一对“神奇串”当且仅当 s 重新排列后可以变成 t。 对于一对“神奇串” s,t ,定义他们为一对“超级神奇串”当且仅当能对它们划分成 k(k≥2)段(设为 s1,s2...sk,t1,t2...tk),使得所有的 1≤i≤k 都满足 si,ti 为一对“神奇串”(看图) 现在给你一个串 s,每次询问一个子串,问是否至少存在一个串使得该串与子串是一对“神奇串”但不是“超级神奇串”题目描述
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": ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1290B/c163083e3bbaacf9e28f6fddff5f78534bd4ddb9.png)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.输入输出格式
输入格式
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.
输出格式
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