3807. [USACO22 Open Silver]Cow Operations

【题目描述】

$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$'。

【样例1输入】

COW
6
1 1
1 2
1 3
2 2
2 3
3 3

【样例1输出】

YNNNYN

【样例1说明】

第一个询问的答案是「是」，因为 $s$ 的第一个字符已经等于 '$C$'。

第五个询问的答案是「是」，因为 $s$ 的第二到第三个字符组成的子串 $OW$ 可以通过两步操作变为 '$C$'：

  $OW$

-> $CWW$

-> $C$

这个样例字符串 $COW$ 的其他子串均不能被转变为 '$C$'。

【样例2输入输出】

点击下载样例2 

【数据规模与约定】

测试点 $2\sim4$：满足 $|s|≤5000，Q≤5000$；

测试点 $5\sim11$：没有额外限制。