luogu#P4979. 矿洞:坍塌

矿洞:坍塌

题目背景

  • Made By tomoo

CYJian家里为什么那么有钱?因为他家&@%#开了矿!!

CYJian家虽然有矿,但是有矿也不能任性。这不,CYJian家的矿塌了......

change:出题人仁慈地放大了空间限制

题目描述

CYJian家的矿塌了之后,就没有经济来源了(不要问我怎么没有存款)。

于是,CYJian迫切地想要修复他家的矿。

CYJian家的矿共出产A,B,CA,B,C三种矿石,所以我们也只能用A,B,CA,B,C三种材料来修复他们家的矿。我们已知共有NN吨材料,每吨材料均为A,B,CA,B,C三种材料中的一种,它们连成了一个串,如:

ABCBCABCBACBCBAAABCBCABCBACBCBAA

CYJian家对材料的要求非常严格,他每次会选择一段连续区间的材料作为修复的材料。因为不合要求的材料会使得矿再次塌陷,砸死CYJian,所以这个连续区间的材料必须满足一下22个要求:

  • 这段连续区间必须是同一种材料
  • 这段连续区间的前一个材料与后一个材料必须不相同。

例如,有一段材料为AACBBABBBCCCBBBAACBBABBBCCCBBB,则(4(4~5)5) 区间的 BBBB(5(5~5)5) 区间的 BB 均符合要求,而 (10(10~12)12) 区间的 CCCCCC 不符合要求。

材料有灵性,所以材料会有变化。

现在有NN吨材料,KK个询问。每个询问是以下的22种形式之一:

  • A x y op 表示替换材料,将xxy(1<=x<=y<=N)y(1<=x<=y<=N)区间内的材料替换为opopopopA,B,CA,B,C三种材料字符中的一个。
  • B x y 表示是否询问,即询问xxy(1<=x<=y<=N)y(1<=x<=y<=N)区间内的材料是否合法,合法输出YesYes,不合法输出NoNo

注意:当x=1x=1y=Ny=N时,你的程序不需要判断前后的情况,而只需要判断区间内的情况.

输入格式

  • 第一行一个正整数NN
  • 接下来NN个字符,表示材料
  • 接下来KK个询问,格式为上述的一种

输出格式

对于每个 B x y 的询问,输出 YesYesNoNo

15
AACBBABBBCCCBBB
3
B 4 5
B 5 5
B 10 12
Yes
Yes
No
5
ABBBB
2
B 1 4
B 2 5
No
Yes

提示

  • 对于3030%的数据,N1000,K2000N\le1000,K\le2000
  • 对于7070%的数据,N5000,K5000N\le5000,K\le5000
  • 对于100100%的数据,N500000,K500000,1<x<=y<NN\le500000,K\le500000,1<x<=y<N