[USACO22OPEN] COW Operations S
题目描述
Bessie 找到了一个长度不超过 $2 \cdot 10^5$ 且仅包含字符 'C','O' 和 'W' 的字符串 $s$。她想知道是否可以使用以下操作将该字符串变为单个字母 'C'(她最喜欢的字母):
1. 选择两个相邻相等的字母并将其删除。
2. 选择一个字母,将其替换为另外两个字母的任一排列。
求出这个字符串本身的答案对 Bessie 而言并不足够,所以她想要知道 $s$ 的 $Q$($1\le Q\le 2\cdot 10^5$)个子串的答案。
输入输出格式
输入格式
输入的第一行包含 $s$。
第二行包含 $Q$。
以下 $Q$ 行每行包含两个整数 $l$ 和 $r$($1\le l\le r\le |s|$,其中 $|s|$ 表示 $s$ 的长度)。
输出格式
输出一个长为 $Q$ 的字符串,如果第 $i$ 个子串可以被转变则第 $i$ 个字符为 'Y',否则为 'N'。
输入输出样例
输入样例 #1
COW
6
1 1
1 2
1 3
2 2
2 3
3 3
输出样例 #1
YNNNYN
说明
【样例解释】
第一个询问的答案是「是」,因为 s 的第一个字符已经等于 'C'。
第五个询问的答案是「是」,因为 s 的第二到第三个字符组成的子串 OW 可以通过两步操作变为 'C':
```
OW
-> CWW
-> C
```
这个样例字符串 COW 的其他子串均不能被转变为 'C'。
【测试点性质】
- 测试点 2-4 满足 $|s|\le 5000$ 以及 $Q\le 5000$。
- 测试点 5-11 没有额外限制。