#P18683. Flower's Land 2
Flower's Land 2
Flower's Land 2
f:“青鱼!快来看看我新出的括号序列题!”
Q:“什么?!这不是一道很有名的题吗?”
f:“呃……那这道怎么样?”
小青鱼和大花字是好朋友。为了庆祝花之国成立17周年,小青鱼设计了一个新游戏。
游戏在一个只由数字0、1、2组成的字符串s=s1s2…sn上进行。每一轮执行以下步骤:
- 选择一个下标i(1≤i<n),使得si=si+1。如果没有这样的下标,游戏立刻结束。
- 删除si和si+1这两个字符,然后回到第一步。
如果能将字符串完全删除、变为空串,玩家获胜;否则玩家失败。删除之后剩余字符按原顺序连接。
为了挑战小青鱼,大花字给出一个长度为n的字符串s,并提出以下两种操作:
1 l r:对每个l≤i≤r,令si←(si+1)mod3。2 l r:设t=s[l…r]=sl sl+1 … sr。如果以t开始上述游戏,判断玩家是否能够获胜。
请帮助小青鱼回答所有询问。询问只是判断,不会实际删除原字符串s中的字符。
输入格式
第一行两个整数n、q(1≤n,q≤500000),分别表示字符串长度和操作数。
第二行一个字符串s,保证长度恰为n,且只含0、1、2。
接下来q行,每行一个操作,格式为1 l r或2 l r。保证1≤l≤r≤n。
输出格式
对每个操作2:如果玩家能将该子串删为空串,输出一行Yes;否则输出一行No。
样例输入
8 9
01211012
2 4 5
2 3 6
1 6 8
1 6 8
2 3 6
2 1 8
1 1 1
1 7 7
2 1 8
样例输出
Yes
No
Yes
No
Yes
样例解释
最初s=01211012。
- 询问s[4…5]=11,可以选择i=1删除这两个字符,获胜,输出Yes。
- 询问s[3…6]=2110,无法删空,输出No。
- 修改6≤i≤8的所有字符,s变为01211120。
- 再次修改6≤i≤8的所有字符,s变为01211201。
- 询问s[3…6]=2112。先选择i=2,删除11,剩下22;再选择i=1,删除22,获胜,输出Yes。
- 询问s[1…8]=01211201,无法删空,输出No。
- 修改位置1,s变为11211201。
- 修改位置7,s变为11211211。
- 询问s[1…8]=11211211,能够删空,输出Yes。