P6894: COW转换
传统题
1.000s
时间限制
256MB
内存限制
3 提交
3 解决
【题目描述】
【题目描述】
Bessie
找到了一个长度不超过 2×10
^5
且仅包含字符 'C'，'O' 和 'W' 的字符串 s。她想知道是否可以使用以下操作将该字符串变为单个字母 'C'
（她最喜欢的字母）：
1.
选择两个相邻相等的字母并将其删除。
2.
选择一个字母，将其替换为另外两个字母的任一排列。
求出这个字符串本身的答案对 Bessie
而言并不足够，所以她想要知道 s
的 Q（1≤Q≤2×10
^5
）个子串的答案。
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 s
。
第二行包含 Q
。
以下 Q
行每行包含两个整数 l 和 r（1≤l≤r≤|s|
，其中 |s|
表示 s 的长度）。
【
输出格式】
（输出至终端 /
标准输出）：
输出一个长为 Q
的字符串，如果第 i 个子串可以被转变则第 i 个字符为 'Y'，否则为 'N'。
【
输入样例】
：
COW
6
1 1
1 2
1 3
2 2
2 3
3 3
【
输出样例】
：
YNNNYN
【样例说明】
第一个询问的答案是「是」，因为 s
的第一个字符已经等于 'C'。
第五个询问的答案是「是」，因为 s
的第二到第三个字符组成的子串 OW 可以通过两步操作变为 'C'：
OW
-> CWW
-> C
这个样例字符串 COW
的其他子串均不能被转变为 'C'。
【
测试点性质】
：
测试点 2-4
满足 |s|≤5000 以及 Q≤5000。
测试点 5-11
没有额外限制。