COW Operations

题目描述

Bessie 找到一个长度至多为 $2 \cdot 10^5$ 的字符串 $s$，只包含三个字符 'C'、'O'、'W'。她想知道是否可以使用以下操作把该字符串变成单个字符 '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$ 个字符为 'Y' 表示第 $i$ 个子串可以被化简为 'C'，否则为 'N'。

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

YNNNYN

提示

第一个询问的答案是 yes，因为 $s$ 的第一个字符本身就等于 'C'。 第五个询问的答案是 yes，因为 $s$ 从第二个到第三个字符的子串 OW 可以通过两次操作转换为 'C'： OW -> CWW -> C 该示例字符串 COW 的其他任何子串都无法化简为 'C' SCORING: 测试点 2-4 满足 $|s|\le 5000$ 且 $Q\le 5000$。 测试点 5-11 没有额外限制。 题目贡献者：Ray Bai

标签: USACO|2022|Silver

来源

USACO|2022|Silver