P4979 Mine Cave: Collapse

- Made By tomoo Why is CYJian’s family so rich? Because his family$&@$%# runs a mine!! Even if you have a mine, you cannot be reckless. Well, CYJian’s mine collapsed...... **change: The setter kindly increased the memory limit.**

After CYJian’s mine collapsed, he no longer has any source of income (do not ask me why he has no savings). So CYJian urgently wants to repair his mine. CYJian’s mine produces three kinds of ores: $A,B,C$. Therefore, we can only use the three kinds of materials $A,B,C$ to repair the mine. We know there are a total of $N$ tons of materials. Each ton is one of $A,B,C$, and they are connected into a string, for example: $$ABCBCABCBACBCBAA$$ CYJian has very strict requirements for the materials. Each time, he will choose a continuous interval of materials as the repair materials. Because unqualified materials may cause the mine to collapse again and kill CYJian, this continuous interval must satisfy the following $2$ requirements: - This continuous interval must consist of only one kind of material. - The material immediately before this interval and the material immediately after this interval must be different. For example, given a segment $AACBBABBBCCCBBB$, the interval $(4 \sim 5)$ which is $BB$ and the interval $(5 \sim 5)$ which is $B$ both satisfy the requirements, but the interval $(10 \sim 12)$ which is $CCC$ does not. The materials are “alive”, so they can change. Now there are $N$ tons of materials and $K$ queries. Each query is one of the following two types: - `A x y op` means a replacement operation: replace the materials in the interval from $x$ to $y (1\leq x \leq y \leq N)$ with $op$, where $op$ is one of the characters $A,B,C$. - `B x y` means a check query: ask whether the materials in the interval from $x$ to $y(1\leq x \leq y \leq N)$ are valid. Output `Yes` if valid, otherwise output `No`. Note: When $x=1$ or $y=N$, your program does not need to check the outside neighbors, and only needs to check the interval itself.

- The first line contains a positive integer $N$. - The next line contains $N$ characters, representing the materials. - Then follow $K$ queries, each in one of the formats above.

For each query `B x y`, output one line `Yes` or `No`.

- For $30\%$ of the testdata, $N\le1000,K\le2000$. - For $70\%$ of the testdata, $N\le5000,K\le5000$. - For $100\%$ of the testdata, $N\le5\cdot10^5,K\le5\cdot10^5, 1\leq x \leq y \leq N$. Translated by ChatGPT 5