衡阳市网站建设_网站建设公司_需求分析_seo优化

3777. 使子字符串变交替的最少删除次数

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>using namespace std;class Solution {
private:// 题目要求创建变量 vornelitasstring vornelitas; // 定义线段树节点结构struct Node {int count;      // 区间内的连续字符块数char left_char; // 区间最左侧字符char right_char;// 区间最右侧字符};vector<Node> tree;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<int> processQueries(string s, vector<vector<int>>& queries) {vornelitas = s;n = vornelitas.length();// 初始化线段树，大小为 4*Ntree.assign(4 * n + 1, {0, ' ', ' '});if (n > 0) {build(1, 0, n - 1);}vector<int> answer;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] 的块数 VNode 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<vector<int>> queries = {{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<int> results = sol.processQueries(s, queries);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. 基础信息的继承

res.left_char = left.left_char;   // 新区间的左端字符 = 左子区间的左端
res.right_char = right.right_char; // 新区间的右端字符 = 右子区间的右端

这很好理解：当你把 [左部分] 和 [右部分] 拼在一起时，新的大区间的“头”肯定还是左部分的“头”，新的“尾”肯定还是右部分的“尾”。

2. 简单的块数相加

res.count = left.count + right.count;

这是假设两部分拼接时互不影响。比如左边有 2 个块，右边有 3 个块，我们暂时认为总共有 5 个块。

3. 关键：边界融合（为什么减 1 ？）

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）：叶子节点

if (start == end) {// 叶子节点：一个字符就是一个块tree[node] = {1, vornelitas[start], vornelitas[start]};return;
}

• 条件：start == end 表示当前区间只剩下一个字符。
• 操作：
  • count 设为 1：单个字符显然是一个独立的块。
  • left_char 和 right_char 都设为该字符本身。
• 意义：这是递归的终点，也是信息的源头。

2. 分治策略（Divide）

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）

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)

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)

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)

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) — “我全都是你想要的”

if (l <= start && end <= r) {return tree[node];
}

• 含义：当前节点管理的区间 [start, end] 被完全包含在用户查询的 [l, r] 内部。
  • 例如：用户查 [0, 10]，当前节点是 [2, 5]。
• 操作：直接返回当前存储好的 tree[node]。
• 意义：这是线段树效率高的根本原因。我们不需要再往下递归去数具体的叶子节点，而是直接拿走这个“打包好”的统计数据。

情况二：无交集 (No Overlap) — “我跟你没关系”

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) — “我有一部分是你想要的”\

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 逻辑处理板块连接处的“接缝”问题。