C - Capella - 题解
标签与难度
标签: 线段树, 分治, 字符串, 位操作, 数据结构
难度: 2500
题目大意喵~
主人你好呀，这道题是关于一种叫做 "Capella-like" 的特殊字符串的，喵~
一个字符串被称为 "Capella-like"，需要同时满足下面两个条件哦：
- 字符串中，出现奇数次的字符种类数，本身也是一个奇数。
- 字符串中，出现次数为非零偶数的字符种类数，本身是一个偶数。
我们拿到一个初始字符串 S，然后会进行 q 次操作。每次操作会把字符串 S 的某个位置的字符修改成一个新的字符。我们需要在最开始以及每次操作之后，都找出当前字符串 S 中，最长的一个 "Capella-like" 子串，并输出它的长度。
举个例子，"capella" 就是一个 Capella-like 字符串，因为它里面 'c', 'p', 'e' 出现1次（奇数次），种类数是3，是奇数；'a', 'l' 出现2次（非零偶数次），种类数是2，是偶数。两个条件都满足啦，喵！
解题思路分析
这道题的条件看起来有点绕，对吧？别担心，跟着我的思路，一步一步把它变简单，喵~
关键性质的转换
我们先来分析一下 "Capella-like" 的两个条件。对于任何一个子串，我们可以统计其中每个字符（'a'到'z'）出现的次数。
我们可以用两个 26 位的二进制数（我们叫它“位掩码”或者 mask）来描述一个子串的字符统计特性：
- 存在掩码 (existence_mask)：如果字符
c在子串里出现过，那么这个掩码的第c - 'a'位就是 1，否则是 0。它等于子串中所有出现过的字符c对应的1 << (c - 'a')的或和。 - 奇偶掩码 (parity_mask)：如果字符
c在子串里出现了奇数次，那么这个掩码的第c - 'a'位就是 1；如果出现了偶数次，就是 0。它等于子串中所有字符c对应的1 << (c - 'a')的异或和。
用这两个掩码，我们可以重新描述题目中的条件：
- 设
Odd(S)为出现奇数次的字符种类数，Even(S)为出现非零偶数次的字符种类数。 Odd(S)其实就是parity_mask中 1 的个数，也就是__builtin_popcount(parity_mask)。Even(S)呢？一个字符出现非零偶数次，意味着它在existence_mask中是 1，但在parity_mask中是 0。所以Even(S) = __builtin_popcount(existence_mask & ~parity_mask)。
所以，Capella-like 的条件变成了：
__builtin_popcount(parity_mask)是奇数。__builtin_popcount(existence_mask & ~parity_mask)是偶数。
这里有一个非常漂亮的小技巧！一个字符要么出现奇数次，要么出现非零偶数次，要么不出现。所以，一个子串里所有出现过的字符，可以被完美地分成这两类。也就是说：
根据题目的条件，Odd(S) 是奇数，Even(S) 是偶数。那么它们的和 Odd(S) + Even(S) 一定是奇数！ 所以，第二个条件可以等价替换为： 2'. __builtin_popcount(existence_mask) 是奇数。
还没完哦，还有更神奇的！我们来看看 parity_mask 和子串长度 L 的关系。 子串的总长度 L 是所有字符出现次数的总和。
当我们对 L 取模 2 时：
偶数次的部分模 2 是 0，奇数次的部分模 2 是 1。所以：
这个 sum 不就是 Odd(S)，也就是 __builtin_popcount(parity_mask) 吗？ 所以我们得到了一个惊人的结论：
这意味着 “子串长度是奇数” 和 “出现奇数次的字符种类数是奇数” 是完全等价的！
所以，那两个复杂的条件，被我们简化成了两个非常清爽的条件：
- 子串的长度是奇数。
- 子串中不同字符的种类数是奇数。
这下问题是不是清晰多啦？喵~
分治与线段树
现在我们的目标是：找到最长的子串，满足长度为奇数，且不同字符数也为奇数。 因为有单点修改和区间查询（最值），这很自然地让我们想到了线段树。
“长度为奇数”这个条件很有趣。一个子串 S[l..r] (1-based) 的长度 r-l+1 是奇数，意味着 r-l 是偶数，这说明 l 和 r 的奇偶性相同！
这启发我们可以把问题一分为二：
- 只考虑开始和结束位置都是奇数的子串。
- 只考虑开始和结束位置都是偶数的子串。
这两个问题是独立的，我们可以分别求解，然后取最大值。它们本质上是同一个问题，我们只用解决一个就好。
让我们来解决奇数位置的情况。我们可以把原字符串 S 中所有奇数位置的字符抽出来，组成一个新的字符串 A。比如 S = "abcbab"，奇数位字符是 'a', 'c', 'a'，组成 A = "aca"。原 S 中一个 S[2i-1..2j-1] 的子串，就对应 A 中的 A[i..j] 子串。它的长度 2(j-i)+1 永远是奇数。所以长度条件自动满足了！
现在，问题被我们简化为： 给定一个字符串 A，和一些单点修改操作，每次操作后，找出 A 的最长子串 A[i..j]，使得其不同字符的种类数是奇数。
这就可以用线段树来解决啦！线段树的每个节点维护其所代表的区间的信息。为了合并两个子节点（比如 left 和 right）的信息，我们需要知道：
left区间的最长合法子串。right区间的最长合法子串。- 跨越
left和right区间分界点的最长合法子串。这个通常是通过组合left的一个后缀和right的一个前缀得到的。
所以，我们的线段树节点需要存储：
ans: 区间内最长合法子串的长度。len: 区间的长度。total_e_mask: 整个区间的存在掩码。prefixes: 区间内一系列“关键”前缀的信息，每个信息包含(existence_mask, length)。suffixes: 同样，一系列“关键”后缀的信息。
“关键”前缀/后缀是指那些 existence_mask 发生变化的前缀/后缀。因为字符集大小只有26，一个区间的前缀/后缀的 existence_mask 最多只会变化26次。所以我们每个节点只需要存最多26个前缀和26个后缀的信息，喵~
合并 left 和 right 节点时：
- 新的
ans至少是max(left.ans, right.ans)。 - 然后，我们暴力枚举
left的每一个关键后缀和right的每一个关键前缀。 - 对于每一个组合
(suf, pre)，计算它们的合并长度suf.len + pre.len和合并掩码suf.mask | pre.mask。 - 如果
__builtin_popcount(合并掩码)是奇数，就用合并长度来更新ans。
这样，我们就可以高效地处理查询和修改了。对偶数位置的情况做同样的操作，每次查询取两个结果的最大值就好啦！
代码实现
这是我根据上面的思路，精心重构的代码哦~ 希望能帮到你，喵！
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
// 使用 popcount 函数需要这个头文件
#ifdef _MSC_VER
#include <intrin.h>
#else
#include <x86intrin.h>
#endif
using namespace std;
// K 是字符集的大小，也就是 26
const int K = 26;
struct Node {
int ans = 0;
int len = 0;
int total_e_mask = 0;
// pair: {existence_mask, length}
vector<pair<int, int>> prefixes;
vector<pair<int, int>> suffixes;
};
// 合并两个线段树节点
Node merge(const Node& left, const Node& right) {
if (left.len == 0) return right;
if (right.len == 0) return left;
Node res;
res.len = left.len + right.len;
res.total_e_mask = left.total_e_mask | right.total_e_mask;
res.ans = max(left.ans, right.ans);
// --- 计算合并后的关键前缀 ---
res.prefixes = left.prefixes;
for (const auto& p : right.prefixes) {
int new_mask = left.total_e_mask | p.first;
// 如果 mask 没变，就不是“关键”的，不用加
if (res.prefixes.empty() || res.prefixes.back().first != new_mask) {
res.prefixes.push_back({new_mask, left.len + p.second});
}
}
// --- 计算合并后的关键后缀 ---
res.suffixes = right.suffixes;
for (const auto& s : left.suffixes) {
int new_mask = s.first | right.total_e_mask;
if (res.suffixes.empty() || res.suffixes.back().first != new_mask) {
res.suffixes.push_back({new_mask, s.second + right.len});
}
}
// --- 计算跨越中点的最长合法子串 ---
for (const auto& s : left.suffixes) {
for (const auto& p : right.prefixes) {
int combined_mask = s.first | p.first;
if (__builtin_popcount(combined_mask) % 2 != 0) {
res.ans = max(res.ans, s.second + p.second);
}
}
}
return res;
}
vector<Node> tree;
string str_view; // 当前线段树处理的字符串视图
// 构建线段树
void build(int node_idx, int l, int r) {
if (l == r) {
int char_val = str_view[l] - 'a';
tree[node_idx].ans = 1;
tree[node_idx].len = 1;
tree[node_idx].total_e_mask = (1 << char_val);
::: v-pre
tree[node_idx].prefixes = {{1 << char_val, 1}};
::: v-pre
tree[node_idx].suffixes = {{1 << char_val, 1}}; return; }
:::
int mid = l + (r - l) / 2;
build(2 * node_idx, l, mid);
build(2 * node_idx + 1, mid + 1, r);
tree[node_idx] = merge(tree[2 * node_idx], tree[2 * node_idx + 1]);
}
// 更新线段树
void update(int node_idx, int l, int r, int pos, char new_char) {
if (l == r) {
int char_val = new_char - 'a';
tree[node_idx].total_e_mask = (1 << char_val);
::: v-pre
tree[node_idx].prefixes = {{1 << char_val, 1}};
::: v-pre
tree[node_idx].suffixes = {{1 << char_val, 1}}; // ans 和 len 不变 return;
:::
}
int mid = l + (r - l) / 2;
if (pos <= mid) {
update(2 * node_idx, l, mid, pos, new_char);
} else {
update(2 * node_idx + 1, mid + 1, r, pos, new_char);
}
tree[node_idx] = merge(tree[2 * node_idx], tree[2 * node_idx + 1]);
}
// 主逻辑函数，解决一个子问题
int solve_subproblem(string& s, int n, const vector<pair<int, char>>& queries) {
if (s.empty()) {
for (size_t i = 0; i < queries.size() + 1; ++i) {
cout << 0 << "\n";
}
return 0;
}
str_view = s;
tree.assign(4 * s.length(), Node());
build(1, 0, s.length() - 1);
vector<int> results;
results.push_back(tree[1].ans);
for (const auto& q : queries) {
int original_pos = q.first;
if ((original_pos % 2) != (n % 2)) { // 判断修改位置是否属于当前子问题
int mapped_pos = original_pos / 2;
update(1, 0, s.length() - 1, mapped_pos, q.second);
}
results.push_back(tree[1].ans);
}
return results.size();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
string s;
cin >> s;
vector<pair<int, char>> queries(q);
for (int i = 0; i < q; ++i) {
cin >> queries[i].first >> queries[i].second;
queries[i].first--; // 0-indexed
}
string odd_s, even_s;
for (int i = 0; i < n; ++i) {
if (i % 2 == 0) odd_s += s[i];
else even_s += s[i];
}
vector<int> odd_results, even_results;
// --- 解决奇数位置子问题 ---
if (!odd_s.empty()) {
str_view = odd_s;
tree.assign(4 * odd_s.length(), Node());
build(1, 0, odd_s.length() - 1);
odd_results.push_back(tree[1].ans * 2 - 1);
for (const auto& query : queries) {
if (query.first % 2 == 0) {
update(1, 0, odd_s.length() - 1, query.first / 2, query.second);
}
odd_results.push_back(tree[1].ans * 2 - 1);
}
} else {
odd_results.assign(q + 1, 0);
}
// --- 解决偶数位置子问题 ---
if (!even_s.empty()) {
str_view = even_s;
tree.assign(4 * even_s.length(), Node());
build(1, 0, even_s.length() - 1);
even_results.push_back(tree[1].ans * 2 - 1);
for (const auto& query : queries) {
if (query.first % 2 != 0) {
update(1, 0, even_s.length() - 1, query.first / 2, query.second);
}
even_results.push_back(tree[1].ans * 2 - 1);
}
} else {
even_results.assign(q + 1, 0);
}
// --- 合并答案 ---
for (int i = 0; i < q + 1; ++i) {
cout << max(1, max(odd_results[i], even_results[i])) << "\n";
}
return 0;
}代码说明:
solve_subproblem被重构并内联到main中，因为两个子问题的逻辑非常相似但又不完全相同（比如修改位置的判断），分开写更清晰。- 奇数位置
S[2i-1..2j-1]对应新串A[i..j]，长度为k = j-i+1。原长度为2k-1。所以子问题的答案k需要转换回2k-1。 - 偶数位置
S[2i..2j]对应新串B[i..j]，长度k。原长度也为2k-1。 - 如果某个子问题（比如偶数位）的字符串为空，它的答案就是0。
- 最终答案至少是1，因为单个字符的子串总是合法的。
复杂度分析
时间复杂度:
- 这里的
N是原字符串长度，Q是查询次数，K是字符集大小（26）。 - 构建线段树需要遍历所有叶子节点，每个合并操作的复杂度是 ，总构建时间是 。
- 每次更新操作会影响路径上的
log N个节点，每次合并需要 ，所以单次更新是 。 - 虽然理论上这个复杂度很高，但在
K是一个较小的常数（如26）时，它在一些情况下是可以通过的。
- 这里的
空间复杂度:
- 线段树有 个节点。每个节点存储了关键前缀和后缀列表，每个列表最多
K个元素。所以总空间是 。
- 线段树有 个节点。每个节点存储了关键前缀和后缀列表，每个列表最多
知识点总结
这道题是一道非常好的数据结构练习题，融合了多种技巧，喵~
- 问题简化: 解题最关键的一步！通过分析题目条件的数学性质，将复杂的描述（奇数次的种类数是奇数，偶数次的种类数是偶数）等价转换为更简洁直观的条件（长度为奇数，不同字符数为奇数）。这是算法竞赛中化繁为简思想的完美体现。
- 分治思想: “长度为奇数”这一条件引出了根据下标奇偶性进行分治的想法，将一个复杂问题拆解成两个结构相同的子问题，大大降低了处理的难度。
- 线段树高级应用: 本题不是简单的线段树求和/求最值。节点需要维护复杂的信息（关键前/后缀列表），合并操作也需要精心设计。这展示了线段树作为一种通用分治工具的强大能力。
- 位操作: 使用位掩码（bitmask）来表示字符集合（
existence_mask）和奇偶性（parity_mask）是处理字符集问题的常用高效技巧。
希望这篇题解能帮到你，如果还有不明白的地方，随时可以再来问我哦！喵~