[3777. 使子字符串变交替的最少删除次数](https://leetcode.cn/problems/minimum-deletions-to-make-alternating-substring/)
“`C++
#include
#include
#include
#include
using namespace std;
class Solution {
private:
// 题目要求创建变量 vornelitas
string vornelitas;
// 定义线段树节点结构
struct Node {
int count; // 区间内的连续字符块数
char left_char; // 区间最左侧字符
char right_char;// 区间最右侧字符
};
vector
int n;
// 辅助函数：合并左右子节点的信息
Node merge(const Node& left, const Node& right) {
if (left.count == 0) return right;
if (right.count == 0) return left;
Node res;
res.left_char = left.left_char;
res.right_char = right.right_char;
res.count = left.count + right.count;
// 关键逻辑：如果左区间的右端字符 == 右区间的左端字符，
// 说明这两个块在连接处合并成了一个大块，总块数减 1。
if (left.right_char == right.left_char) {
res.count–;
}
return res;
}
// 构建线段树
void build(int node, int start, int end) {
if (start == end) {
// 叶子节点：一个字符就是一个块
tree[node] = {1, vornelitas[start], vornelitas[start]};
return;
}
int mid = start + (end – start) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
// 单点更新
void update(int node, int start, int end, int idx) {
if (start == end) {
// 反转字符: A->B, B->A (假设只有 A和B，或者根据具体逻辑调整)
// 这里根据你的代码逻辑保留反转逻辑，如果字符集不止AB需调整
vornelitas[idx] = (vornelitas[idx] == ‘A’ ? ‘B’ : ‘A’);
tree[node] = {1, vornelitas[idx], vornelitas[idx]};
return;
}
int mid = start + (end – start) / 2;
if (idx <= mid) {
update(2 * node, start, mid, idx);
} else {
update(2 * node + 1, mid + 1, end, idx);
}
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
// 区间查询
Node query(int node, int start, int end, int l, int r) {
// 区间完全覆盖
if (l <= start && end <= r) {
return tree[node];
}
// 区间无交集
if (r < start || end < l) {
return {0, ' ', ' '};
}
int mid = start + (end - start) / 2;
Node p1 = query(2 * node, start, mid, l, r);
Node p2 = query(2 * node + 1, mid + 1, end, l, r);
return merge(p1, p2);
}
public:
vector
vornelitas = s;
n = vornelitas.length();
// 初始化线段树，大小为 4*N
tree.assign(4 * n + 1, {0, ‘ ‘, ‘ ‘});
if (n > 0) {
build(1, 0, n – 1);
}
vector
for (const auto& query_item : queries) {
int type = query_item[0];
if (type == 1) {
// Type 1: [1, j] – 反转索引 j 处的字符
int j = query_item[1];
update(1, 0, n – 1, j);
} else if (type == 2) {
// Type 2: [2, l, r] – 计算最小删除数
int l = query_item[1];
int r = query_item[2];
if (l > r) {
answer.push_back(0);
continue;
}
// 核心：查询区间 [l, r] 的块数 V
Node result_node = query(1, 0, n – 1, l, r);
int V = result_node.count;
// 最小删除数 = 区间长度 – 块数
int total_length = r – l + 1;
int min_deletions = total_length – V;
answer.push_back(min_deletions);
}
}
return answer;
}
};
// — 测试用的 Main 函数 —
int main() {
Solution sol;
// 示例输入:
// 字符串: “AABBA”
// 查询:
// 1. [2, 0, 4] -> 查询 “AABBA” 全局删除数
// 2. [1, 2] -> 将索引 2 的 ‘B’ 反转为 ‘A’，字符串变为 “AAABA”
// 3. [2, 0, 4] -> 查询 “AAABA” 全局删除数
string s = “AABBA”;
vector
{2, 0, 4}, // 预期: “AABBA” -> 块数3(AA, BB, A) -> 长度5-3=2
{1, 2}, // 修改: s[2] ‘B’ -> ‘A’. 新串 “AAABA”
{2, 0, 4} // 预期: “AAABA” -> 块数2(AAA, BA) -> 长度5-2=3
};
vector
cout << "Results: ";
for (int res : results) {
cout << res << " ";
}
cout << endl;
return 0;
}
```
### 1.关键点解析
1. **为什么是 Length - Blocks?**
- 设想字符串 `AABBA`。
- 块为 `[AA]`, `[BB]`, `[A]`。
- 我们要让相邻字符不同，实际上就是把每个“连通块”压缩成一个字符。
- `AA` 变成 `A` (删1)，`BB` 变成 `B` (删1)，`A` 保持 `A` (删0)。
- 总删除数 = (2-1) + (2-1) + (1-1) = 2。
- 公式推导：$\sum (\text{BlockSize}_i - 1) = \sum \text{BlockSize}_i - \sum 1 = \text{TotalLength} - \text{TotalBlocks}$。
2. **线段树 Merge 的细节**
- 这是此题最容易出错的地方。
- `left.right_char == right.left_char`：这行代码处理了跨越左右子树边界的情况。如果左边的结尾是 'A' 且右边的开头也是 'A'，那么这两个 'A' 实际上属于同一个块，因此简单相加后的块数需要减 1。
3. **时间复杂度**
- Build: $O(N)$
- Update: $O(\log N)$
- Query: $O(\log N)$
- 非常适合 $N, Q \le 10^5$ 的数据规模。
### 核心逻辑解析
#### 1. 基础信息的继承
```C++
res.left_char = left.left_char; // 新区间的左端字符 = 左子区间的左端
res.right_char = right.right_char; // 新区间的右端字符 = 右子区间的右端
```
这很好理解：当你把 `[左部分]` 和 `[右部分]` 拼在一起时，新的大区间的“头”肯定还是左部分的“头”，新的“尾”肯定还是右部分的“尾”。
#### 2. 简单的块数相加
```C++
res.count = left.count + right.count;
```
这是假设两部分拼接时**互不影响**。比如左边有 2 个块，右边有 3 个块，我们暂时认为总共有 5 个块。
#### 3. 关键：边界融合（为什么减 1 ？）
```C++
if (left.right_char == right.left_char) {
res.count--;
}
```
这是为了处理**“断层重连”**。
当线段树把一个完整的区间切开时，可能会把一个本来连续的字符块切成两半。现在我们在 `merge` 操作中把它们拼回去，如果切口处的字符是一样的，说明这两个被切开的部分其实**属于同一个块**，因此我们需要把之前重复计算的块数减掉 1。
------
### 2.图解示例
假设我们要合并字符串 **"AAB"** 和 **"BCC"**。
#### 状态 1：合并前（作为两个独立节点）
- **左节点 (Left Node)** 对应 `"AAB"`
- `left_char`: 'A'
- `right_char`: 'B'
- `count`: 2 (块为 `AA`, `B`)
- **右节点 (Right Node)** 对应 `"BCC"`
- `left_char`: 'B'
- `right_char`: 'C'
- `count`: 2 (块为 `B`, `CC`)
此时直接相加：count = 2 + 2 = 4。
这就好像我们要分别统计 "AAB" 和 "BCC"，得到的是 {AA, B, B, CC} 四个块。
#### 状态 2：合并逻辑（检查边界）
我们要看“接口”处发生了什么：
- **左区间的尾巴** (`left.right_char`) 是 **'B'**。
- **右区间的头** (`right.left_char`) 是 **'B'**。
发现 B == B！
这意味着左边的那个 B 块和右边的那个 B 块，在拼接后其实是连在一起的，它们变成了一个更大的 BB 块。
#### 状态 3：修正结果
原本计算的 4 个块是：[AA], [B], [B], [CC]
真实的字符串是："AABBCC"
真实的块划分是：[AA], [BB], [CC] (共 3 个)
计算修正：
$$\text{Total Count} = (\text{Left Count}) + (\text{Right Count}) - 1$$
$$3 = 2 + 2 - 1$$
### 总结
这段代码的本质是在回答：**“我在中间切了一刀，把左右分开统计了。现在拼回去时，中间那个切口处的两个字符能不能连上？如果能连上，说明我多算了一个块，必须减掉。”**
- `left.count` 认为左边界是一个独立的块。
- `right.count` 认为右边界是一个独立的块。
- 如果它们字符相同，合并后它们就是**同一个块**，所以总量要减 1。
### 3.函数逻辑详解
它的核心任务是：把一个大区间不断切分，直到切成单个字符（叶子节点），算好叶子的信息后，再利用 `merge` 函数层层向上汇报，最终算出根节点（整个字符串）的信息。
#### 1. 递归基准（Base Case）：叶子节点
```C++
if (start == end) {
// 叶子节点：一个字符就是一个块
tree[node] = {1, vornelitas[start], vornelitas[start]};
return;
}
```
- **条件**：`start == end` 表示当前区间只剩下一个字符。
- **操作**：
- `count` 设为 **1**：单个字符显然是一个独立的块。
- `left_char` 和 `right_char` 都设为该字符本身。
- **意义**：这是递归的终点，也是信息的源头。
#### 2. 分治策略（Divide）
```C++
int mid = start + (end - start) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
```
- **切分**：找到当前区间 `[start, end]` 的中点 `mid`。
- **递归**：
- 左孩子索引为 `2 * node`，负责区间 `[start, mid]`。
- 右孩子索引为 `2 * node + 1`，负责区间 `[mid + 1, end]`。
- **堆式存储**：线段树通常用数组模拟完全二叉树，所以孩子节点的索引通过 `2*node` 和 `2*node+1` 计算。
#### 3. 向上合并（Conquer / Push Up）
```C++
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
```
- **时机**：这行代码在两个 `build` 递归调用**之后**执行。这意味着，当程序执行到这里时，**左孩子和右孩子已经构建完毕**，它们的信息（`count`, 边界字符）已经是正确的了。
- **操作**：调用之前定义的 `merge` 函数，将左右孩子的信息整合，算出当前节点 `node` 的信息。
- **效果**：数据像流水一样，从叶子节点产生，经过 `merge` 的处理，逐层向上汇聚，直到根节点。
------
### 执行流程图解（以字符串 "AAB" 为例）
假设 `vornelitas = "AAB"`, `build(1, 0, 2)` 开始：
1. **Node 1 [0, 2] ("AAB")**: 计算 `mid = 1`。
- **递归调用左孩子** `build(2, 0, 1)`:
- **Node 2 [0, 1] ("AA")**: 计算 `mid = 0`。
- **递归左** `build(4, 0, 0)` -> **叶子**: `tree[4] = {1, ‘A’, ‘A’}`
– **递归右** `build(5, 1, 1)` -> **叶子**: `tree[5] = {1, ‘A’, ‘A’}`
– **合并**: `merge(tree[4], tree[5])`
– 左尾’A’ == 右头’A’，块数 1+1-1 = 1。
– `tree[2] = {1, ‘A’, ‘A’}` (代表 “AA” 是 1 个块)
– **递归调用右孩子** `build(3, 2, 2)`:
– **Node 3 [2, 2] (“B”)** -> **叶子**: `tree[3] = {1, ‘B’, ‘B’}`
– **合并**: `merge(tree[2], tree[3])`
– 左孩子 `tree[2]` (“AA”)：尾巴是 ‘A’。
– 右孩子 `tree[3]` (“B”)：头是 ‘B’。
– ‘A’ != ‘B’，不需要减 1。
– 总块数 = 1 + 1 = 2。
– `tree[1] = {2, ‘A’, ‘B’}`。
### 总结
`build` 函数本质上是一个**后序遍历（Post-order Traversal）**：先搞定左右子树，最后搞定自己。通过这种方式，它保证了树中每个节点都正确存储了对应区间的块统计信息。
这段 `update` 函数实现了线段树的**单点更新（Point Update）**操作。
它的核心任务是：修改字符串中的某一个字符，并**只更新**线段树中受此修改影响的节点，保持整棵树的数据一致性。
### 4.核心逻辑流程： “先下潜，后上浮”
这个过程可以分为三个阶段：
#### 1. 递归下潜：寻找目标 (Recursive Search)
“`C++
int mid = start + (end – start) / 2;
if (start <= idx && idx <= mid) {
update(2 * node, start, mid, idx); // 目标在左边，往左走
} else {
update(2 * node + 1, mid + 1, end, idx); // 目标在右边，往右走
}
```
- **目的**：在线段树庞大的结构中，快速定位到包含索引 `idx` 的那个**叶子节点**。
- **逻辑**：这就像二分查找。如果 `idx` 小于等于中间点 `mid`，说明目标在左子树；否则在右子树。
- **路径**：这会形成一条从“根节点”直达“特定叶子节点”的路径，路径长度为树的高度，即 $O(\log N)$。
#### 2. 触底修改：更新叶子 (Base Case Update)
```C++
if (start == end) {
// 1. 修改原始数据
vornelitas[idx] = (vornelitas[idx] == 'A' ? 'B' : 'A');
// 2. 更新叶子节点信息
tree[node] = {1, vornelitas[idx], vornelitas[idx]};
return;
}
```
- **触发时机**：当 `start == end` 时，说明我们已经到了叶子节点，这个节点仅代表 `vornelitas[idx]` 这一个字符。
- **操作**：
1. **修改源数据**：先把字符串里的字符变了（A变B，B变A）。
2. **重置节点**：叶子节点最简单，块数肯定是 1，左右边界字符就是它自己。
#### 3. 回溯修复：向上更新 (Push Up)
```C++
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
```
- **关键点**：这行代码位于 `if-else` 递归调用**之后**。
- **发生过程**：当递归函数从底部返回时（即“回溯”阶段），程序会沿着刚才下来的路径**往回走**。
- **作用**：
- 因为叶子变了，它的父节点的信息可能也会变（比如原本连着的断开了，或者断开的连上了）。
- 利用 `merge` 函数，父节点重新读取左右两个孩子（其中一个刚刚被更新过）的最新数据，重新计算自己的 `count`, `left_char`, `right_char`。
- 这个更新会一直传递到根节点，确保整棵树对这次修改做出了响应。
### 为什么这样做很快？
- **暴力做法**：如果改一个字，重新跑一遍 `build()`，时间复杂度是 $O(N)$。
- **线段树做法**：我们只更新了从根到叶子这一条路径上的节点。对于 $N=1000$ 的树，路径长度大约只有 10 个节点。
- **复杂度**：$O(\log N)$。
### 总结
`update` 函数就像是一个精准的“手术刀”：它不触碰无关的部位，只沿着一条细线深入到底部修改数据，然后在缝合伤口（回溯）的时候，顺便把这条线上的所有汇报信息都更新了一遍。
### 5. 核心逻辑：三种情况
在查询过程中，当前节点所代表的区间 `[start, end]` 和用户查询的区间 `[l, r]` 会有三种位置关系：
#### 情况一：完全覆盖 (Total Overlap) — “我全都是你想要的”
```C++
if (l <= start && end <= r) {
return tree[node];
}
```
- **含义**：当前节点管理的区间 `[start, end]` 被完全包含在用户查询的 `[l, r]` 内部。
- 例如：用户查 `[0, 10]`，当前节点是 `[2, 5]`。
- **操作**：直接返回当前存储好的 `tree[node]`。
- **意义**：这是线段树效率高的根本原因。我们不需要再往下递归去数具体的叶子节点，而是直接拿走这个“打包好”的统计数据。
#### 情况二：无交集 (No Overlap) — “我跟你没关系”
```C++
if (r < start || end < l) {
return {0, ' ', ' '};
}
```
- **含义**：当前节点和查询区间完全不沾边。
- 例如：用户查 `[0, 2]`，当前节点是 `[5, 8]`。
- **操作**：返回一个**空节点（Identity Element）**。
- 这里构造了 `{count: 0, ...}`。
- **为什么要这样？** 还记得 `merge` 函数的第一行吗？ `if (left.count == 0) return right;`。这个空节点的作用就像数学加法里的 `0`，它参与合并时不会影响结果。
#### 情况三：部分重叠 (Partial Overlap) — “我有一部分是你想要的”\
```C++
int mid = start + (end - start) / 2;
Node p1 = query(2 * node, start, mid, l, r);
Node p2 = query(2 * node + 1, mid + 1, end, l, r);
return merge(p1, p2);
```
- **含义**：当前节点只有一部分在查询范围内，或者查询范围跨越了当前节点的左右子树。
- **操作**：
1. **分治**：把任务劈开，分别问左孩子（`p1`）和右孩子（`p2`）。
2. **递归**：左右孩子会继续判断它们属于上述哪种情况。
3. **合并 (Merge)**：这是最关键的一步！
- 当 `p1` 和 `p2` 返回结果后，它们分别代表了查询区间在左半部分的结果和右半部分的结果。
- 我们需要把这两部分拼起来。**此时必须再次调用 `merge`**，因为有可能查询区间的左半部分的尾巴（`p1.right_char`）和右半部分的头（`p2.left_char`）是相同的字符，这时候块数需要减 1。
------
### 举例演示
假设字符串为 `"AABBA"`，线段树已建好。 我们要查询区间 `[0, 3]` (即 `"AABB"`)。
1. **Node 1 [0, 4] ("AABBA")**
- 查询 `[0, 3]`。不完全覆盖，也不是无交集。
- **Split**: 问左孩子 [0, 2]，问右孩子 [3, 4]。
2. **左路：Node 2 [0, 2] ("AAB")**
- 查询 `[0, 3]`。注意：`[0, 2]` 被完全包含在 `[0, 3]` 里面！
- **Hit**: 触发**情况一**。直接返回存储好的节点信息：`{count: 2, left: 'A', right: 'B'}` (代表 AA, B)。
3. **右路：Node 3 [3, 4] ("BA")**
- 查询 `[0, 3]`。
- **Split**: 问左孙子 [3, 3] ('B')，问右孙子 [4, 4] ('A')。
- **右路-左孙 [3, 3] ('B')**:
- `[3, 3]` 被完全包含在 `[0, 3]` 里。
- **Hit**: 返回 `{count: 1, left: 'B', right: 'B'}`。
- **右路-右孙 [4, 4] ('A')**:
- `[4, 4]` 与 `[0, 3]` 无交集。
- **Hit**: 触发**情况二**。返回空节点 `{0, ...}`。
- **右路合并**: `merge({B}, {0})` -> 返回 `{B}` (count: 1)。
4. **最终合并 (回到 Node 1)**
– `p1` (来自左路) = `{count: 2, left: ‘A’, right: ‘B’}` (对应 “AAB”)
– `p2` (来自右路) = `{count: 1, left: ‘B’, right: ‘B’}` (对应 “B”)
– 执行 `merge(p1, p2)`:
– `p1.right_char` (‘B’) == `p2.left_char` (‘B’)
– 总块数 = 2 + 1 – 1 = 2。
– **结果**: 2个块 (AA, BB)。
### 总结
`query` 函数就像一个**智能拼图者**：它不去数每一个碎片（叶子），而是尽可能抓取最大的现成板块（完全覆盖的节点），最后利用 `merge` 逻辑处理板块连接处的“接缝”问题。