给你一个下标从 0 开始的字符串 s 。另给你一个下标从 0 开始、长度为 k 的字符串 queryCharacters ，一个下标从 0 开始、长度也是 k 的整数 下标 数组 queryIndices ，这两个都用来描述 k 个查询。

第 i 个查询会将 s 中位于下标 queryIndices[i] 的字符更新为 queryCharacters[i] 。

返回一个长度为 k 的数组 lengths ，其中 lengths[i] 是在执行第 i 个查询 之后 s 中仅由 单个字符重复 组成的 最长子字符串 的 长度 。

示例 1：

输入：s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3]
输出：[3,3,4]
解释：
- 第 1 次查询更新后 s = "bbbacc" 。由单个字符重复组成的最长子字符串是 "bbb" ，长度为 3 。
- 第 2 次查询更新后 s = "bbbccc" 。由单个字符重复组成的最长子字符串是 "bbb" 或 "ccc"，长度为 3 。
- 第 3 次查询更新后 s = "bbbbcc" 。由单个字符重复组成的最长子字符串是 "bbbb" ，长度为 4 。
因此，返回 [3,3,4] 。
示例 2：

输入：s = "abyzz", queryCharacters = "aa", queryIndices = [2,1]
输出：[2,3]
解释：
- 第 1 次查询更新后 s = "abazz" 。由单个字符重复组成的最长子字符串是 "zz" ，长度为 2 。
- 第 2 次查询更新后 s = "aaazz" 。由单个字符重复组成的最长子字符串是 "aaa" ，长度为 3 。
因此，返回 [2,3] 。
 

提示：

讯享网

1 <= s.length <= 10^5
s 由小写英文字母组成
k == queryCharacters.length == queryIndices.length
1 <= k <= 10^5
queryCharacters 由小写英文字母组成
0 <= queryIndices[i] < s.length

思路：比较经典的线段树可解决问题。构建一颗支持单点更新的普通线段树即可，线段树上每个节点维护：当前区间的最长单字符前缀、最长单字符后缀、区间最长单字符长度、左端点字符、右端点字符、区间左右端点位置。

合并两个子区间时，如果前一个区间的末尾字符等于后一个区间的第一个字符，则可以合并这两个区间:

1. 如果前一个区间仅由单个字符组成，则可以更新合并后的前缀最大长度。

2. 如何后一个区间仅由单个字符组成，则可以更新合并后的后缀最大长度。

3. 区间的最大单字符长度也要同时更新。

写法主要参考：优秀题解

class Solution { public: static const int N = 4e5 + 10; string s; struct TreeNode { int l, r, size; char lc, rc; int lmax, rmax, dmax; }tr[N]; void pushup(TreeNode &f, TreeNode &l, TreeNode &r) { f.lmax = l.lmax, f.rmax = r.rmax, f.dmax = max(l.dmax, r.dmax); f.lc = l.lc; f.rc = r.rc; f.size = l.size + r.size; if (l.rc == r.lc) { if (l.rmax == l.size) f.lmax += r.lmax; if (r.lmax == r.size) f.rmax += l.rmax; f.dmax = max(f.dmax, l.rmax + r.lmax); } } void build(int id, int l, int r) { if (l == r) { tr[id] = {l, l, 1, s[l - 1], s[l-1], 1, 1, 1}; return; } tr[id].l = l; tr[id].r = r; int mid = (l + r) / 2; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); pushup(tr[id], tr[id * 2], tr[id * 2 + 1]); } TreeNode query(int id, int l, int r) { if (tr[id].l >= l && tr[id].r <= r) { return tr[id]; } int mid = (tr[id].l + tr[id].r) / 2; if (r <= mid) return query(id * 2, l, r); else if (l > mid) return query(id * 2 + 1, l, r); else { TreeNode lt = query(id * 2, l, r); TreeNode rt = query(id * 2 + 1, l, r); TreeNode tmp; pushup(tmp, lt, rt); return tmp; } } void modify(int id, int x, char y) { if (tr[id].l == x && tr[id].r == x) { tr[id] = {x, x, 1, y, y, 1, 1, 1}; return; } int mid = (tr[id].l + tr[id].r) / 2; if (x <= mid) modify(id * 2, x, y); else if (x > mid) modify(id * 2 + 1, x, y); pushup(tr[id], tr[id * 2], tr[id * 2 + 1]); } vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) { this->s = s; build(1, 1, s.size()); vector<int> ans; for (int i = 0; i < queryIndices.size(); i++) { modify(1, queryIndices[i] + 1, queryCharacters[i]); ans.push_back(query(1, 1, s.size()).dmax); } return ans; } };