矿洞：坍塌
一、题目描述
\(CYJian\)家的矿塌了之后，就没有经济来源了（不要问我怎么没有存款）。
于是，\(CYJian\)迫切地想要修复他家的矿。
\(CYJian\)家的矿共出产\(A,B,C\)三种矿石，所以我们也只能用\(A,B,C\)三种材料来修复他们家的矿。
我们已知共有\(N\)吨材料，每吨材料均为\(A,B,C\)三种材料中的一种，它们连成了一个串，如：
\[ABCBCABCBACBCBAA \]\(CYJian\)家对材料的要求非常严格，他每次会选择一段连续区间的材料作为修复的材料。因为不合要求的材料会使得矿再次塌陷，砸死\(CYJian\)，所以这个连续区间的材料必须满足一下\(2\)个要求：
- 这段连续区间必须是同一种材料
- 这段连续区间的前一个材料与后一个材料必须不相同。
例如，有一段材料为\(AACBBABBBCCCBBB\)，则\((4\)~\(5)\) 区间的 \(BB\) 和 \((5\)~\(5)\) 区间的 \(B\) 均符合要求，而 \((10\)~\(12)\) 区间的 \(CCC\) 不符合要求。
材料有灵性，所以材料会有变化。
现在有\(N\)吨材料，\(K\)个询问。每个询问是以下的\(2\)种形式之一：
- \(A\) \(x\) \(y\) \(op\) 表示替换材料，将\(x\)到\(y(1<=x<=y<=N)\)区间内的材料替换为\(op\)，\(op\)为\(A,B,C\)三种材料字符中的一个。
- \(B\) \(x\) \(y\) 表示是否询问，即询问\(x\)到\(y(1<=x<=y<=N)\)区间内的材料是否合法，合法输出\(Yes\)，不合法输出\(No\)。
注意:当\(x=1\)或\(y=N\)时,你的程序不需要判断前后的情况,而只需要判断区间内的情况.
输入格式
- 第一行一个正整数\(N\)
- 接下来\(N\)个字符，表示材料
- 接下来\(K\)个询问，格式为上述的一种
输出格式
对于每个 B x y 的询问，输出 \(Yes\) 或 \(No\)
样例输入 #1
15
AACBBABBBCCCBBB
3
B 4 5
B 5 5
B 10 12
样例输出 #1
Yes
Yes
No
提示
- 对于\(30\)%的数据，\(N\le1000,K\le2000\)
- 对于\(70\)%的数据，\(N\le5000,K\le5000\)
- 对于\(100\)%的数据，\(N\le500000,K\le500000,1<x<=y<N\)
二、线段树解法
- 每个字母赋一个不同的值，范围要大。
- 维护区间和
#include <bits/stdc++.h>
const int N = 1000010;
using namespace std;
// 线段树模板
#define int long long
#define tu tr[u] // u节点,Node类型
#define ln u << 1 // u节点的左儿子编号,整数类型
#define rn u << 1 | 1 // u节点的右儿子编号,整数类型
#define ls tr[ln] // u节点的左儿子节点,Node类型
#define rs tr[rn] // u节点的右儿子节点,Node类型
struct Node {
int l, r;
int sum, tag;
} tr[N];
int a[N];
int n, m;
// 通过左右儿子的信息，向上汇总父节点的统计信息
void pushup(int u) {
tu.sum = ls.sum + rs.sum;
}
/*
功能：初始化线段树
①如果有初始值需要向线段树中初始化，才需要build，否则不需要进行build
②初始化一般在if(l==r)中进行，一般对区间和进行初始化tu.sum=a[l]
③由于进行了初始化操作，所以，必须进行pushup对父节点进行统计信息更新
*/
void build(int u, int l, int r) {
tu.l = l, tu.r = r;
if (l == r) {
tu.sum = a[l]; // 初始化线段树
return;
}
int mid = (l + r) >> 1;
build(ln, l, mid);
build(rn, mid + 1, r);
// 因为构建时初始化了线段树，所以，需要向上推送汇总统计信息
pushup(u);
}
// 向下推送懒标记
void pushdown(int u) {
if (tu.tag) {
ls.tag = rs.tag = tu.tag; // 左儿子懒标记=右儿子懒标记=传递下来的懒标记
// 因为整体被赋值为v,所以左儿子的区间和=左儿子的区间长度 乘以 传递下来的懒标记
ls.sum = (ls.r - ls.l + 1) * tu.tag;
rs.sum = (rs.r - rs.l + 1) * tu.tag; // 右儿子同理
tu.tag = 0; // 向下传递懒标记完毕，将父节点的懒标记修改为0
}
}
// 整体区间赋值为v
void modify(int u, int l, int r, int v) { // 整体区间赋值为v
if (tu.l >= l and tu.r <= r) {
tu.sum = (tu.r - tu.l + 1) * v; // sum和=区间长度*v
tu.tag = v; // 懒标记=v
return; // 不再继续向下传递
}
pushdown(u); // 如果存在懒标记，在分裂前就下传懒标记
int mid = (tu.l + tu.r) >> 1;
if (l <= mid) modify(ln, l, r, v);
if (r > mid) modify(rn, l, r, v);
pushup(u);
}
// 区间查询
int query(int u, int l, int r) {
if (tu.l >= l and tu.r <= r) return tu.sum;
int res = 0;
pushdown(u);
int mid = (tu.l + tu.r) >> 1;
if (l <= mid) res += query(ln, l, r);
if (r > mid) res += query(rn, l, r);
return res;
}
// 将字符映射成数字
int get(char op) {
if (op == 'A') return op * 1234;
if (op == 'B') return op * 12345;
if (op == 'C') return op * 123456;
}
/*[l,r]之间是不是全是A、B、C？
方法：整数HASH（我给起的名字）
步骤：1、A=1234 B=12345 C=123456
2、如果区间内全是A，则区间长度(r-l+1)*1234=sum
3、如果区间内全是B，则区间长度(r-l+1)*12345=sum
4、如果区间内全是C，则区间长度(r-l+1)*123456=sum
*/
bool check(int sum, char c, int l, int r) {
if (c == 'A') return sum == c * 1234 * (r - l + 1);
if (c == 'B') return sum == c * 12345 * (r - l + 1);
if (c == 'C') return sum == c * 123456 * (r - l + 1);
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("P4979.in", "r", stdin);
#endif
// 加快读入
ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
char op;
cin >> op;
a[i] = get(op);
}
build(1, 1, n);
int l, r;
cin >> m;
while (m--) {
char op;
cin >> op;
if (op == 'A') { // 区间替换操作
char x;
cin >> l >> r;
cin >> x; // 替换成啥
modify(1, l, r, get(x));
} else {
cin >> l >> r;
int sum = query(1, l, r);
// 区间内是不是都是一样的字符
if ((!check(sum, 'A', l, r) && !check(sum, 'B', l, r) && !check(sum, 'C', l, r))) {
puts("No");
continue;
}
// l=1时，没有前面的内容;r=n时，没有后面的内容，这两种情况，不需要检查是不是前后一致，只需要检查区间内是不是都是一样的即可
if (l == 1 || r == n) {
puts("Yes");
continue;
}
// 执行到这里，肯定是区间内都是一样的,并且，l>1 && r<n
if (query(1, l - 1, l - 1) != query(1, r + 1, r + 1))
puts("Yes");
else
puts("No");
}
}
return 0;
}
三、柯朵莉树解法
注：需要\(O^2\)优化才能过掉，否则会被卡住\(3\)个测试点
#include <bits/stdc++.h>
using namespace std;
// 柯朵莉树模板
struct Node {
int l, r, v;
bool operator<(const Node &b) const {
return l < b.l;
}
};
set<Node> s;
set<Node>::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;
}