#include using namespace std; // 柯朵莉树模板 struct Node { int l, r, v; bool operator<(const Node &b) const { return l < b.l; } }; set s; set::iterator split(int x) { auto it = s.lower_bound({x}); if (it != s.end() && it->l == x) return it; --it; int L = it->l, R = it->r, V = it->v; s.erase(it); s.insert({L, x - 1, V}); return s.insert({x, R, V}).first; } void assign(int l, int r, int v) { auto R = split(r + 1), L = split(l); s.erase(L, R); s.insert({l, r, v}); } int main() { #ifndef ONLINE_JUDGE freopen("P4979.in", "r", stdin); #endif // 加快读入 ios::sync_with_stdio(false), cin.tie(0); int n; cin >> n; // n个字符,表示材料 int st = 1; // 区间起点start char x; cin >> x; int a = x; // a:当前字符 int b = a; // b:当前的前一个字符 for (int i = 2; i <= n; i++) { cin >> x; a = x; // 读入一个字符 if (a != b) { // 如果两个字符不一致,说明开始的新的区间 s.insert({st, i - 1, b}); // 记录上一个区间 st = i; // 记录新的区间起点 } b = a; // 修改前一个字符 } s.insert({st, n, a}); // 将尾巴打扫干净 int m; // m次操作 cin >> m; while (m--) { cin >> x; int l, r; cin >> l >> r; if (x == 'A') { // 替换材料 char op; cin >> op; assign(l, r, op); // 区间平推op } else { // 询问[l,r]区间内的材料是否合法 auto R = split(r + 1), L = split(l); /* 此时我们想进行一次推平操作,把[2,8]区间内的元素都改成666.首先我们发现,[8,10]是一个区间, 那么需要先split(9),把[8,8]和[9,10]拆成两个区间。 同理,原来的[1,2]区间,也需要拆成[1,1]和[2,2]。 */ // 注意:当x=1或y=N时,你的程序不需要判断前后的情况,而只需要判断区间内的情况. if (l > 1 && r < n) { // 之所以要判断是不是l>1,是因为下面需要检查前面的区间块,而l=1时,是没有前面的区间块的 // 同理,r < n,是因为r=n时,是没有后面的区间块的 L--; // 前面的区间块,迭代器只能加加减减,有借有还 if (L->v == R->v) { // 如果前面区间的字符与后面区间的字符一样,根据题意,输出NO puts("No"); continue; } L++; // 还原迭代器到原始L区间上,迭代器只能加加减减,有借有还 } // 检查区间内的值是不是一致,L未能如期到达R,输出NO auto t = L; for (; L != R; L++) { if (L->v != t->v) break; } if (L != R) puts("No"); else puts("Yes"); // 检查是同一个区域的进行整理,合并,起到优化作用,不加上会TLE三个点 assign(t->l, (--L)->r, t->v); // --L是最后一个匹配位置,合并[t,--L] } } return 0; }