P8271 [USACO22OPEN] COW Operations S

Bessie found a string $s$ of length at most $2 \cdot 10^5$ that contains only the characters 'C', 'O', and 'W'. She wants to know whether she can use the following operations to turn the string into a single letter 'C' (her favorite letter): 1. Choose two adjacent equal letters and delete them. 2. Choose one letter and replace it with any permutation of the other two letters. Knowing the answer for the whole string alone is not enough for Bessie, so she wants to know the answers for $Q$ ($1 \le Q \le 2 \cdot 10^5$) substrings of $s$.

The first line contains $s$. The second line contains $Q$. The next $Q$ lines each contain two integers $l$ and $r$ ($1 \le l \le r \le |s|$), where $|s|$ is the length of $s$.

Output a string of length $Q$. If the $i$-th substring can be transformed, then the $i$-th character should be 'Y', otherwise it should be 'N'.

[Sample Explanation] The answer to the first query is "Yes", because the first character of $s$ is already equal to 'C'. The answer to the fifth query is "Yes", because the substring formed by the second to third characters of $s$, namely OW, can be turned into 'C' in two operations: ``` OW -> CWW -> C ``` All other substrings of the sample string COW cannot be transformed into 'C'. [Test Point Properties] - Test points 2-4 satisfy $|s| \le 5000$ and $Q \le 5000$. - Test points 5-11 have no additional constraints. Translated by ChatGPT 5