题目解析

本题要求维护一个字符串，支持单点修改，并在每次修改后计算该字符串的所有子序列中至少出现两次的不同非空子序列的数量。由于直接枚举所有子序列不可行（指数级复杂度），需要采用高效的数据结构来维护相关信息。

核心思路

代码使用线段树来维护字符串的区间信息。每个线段树节点存储一个结构体 Info，其中包含：

• f矩阵（7×7）：用于状态转移统计，可能表示从自动机状态i到状态j的方案数。状态0-5对应字母'a'到'f'，状态6可能表示起始状态或空序列。矩阵乘法用于合并区间时的状态转移。
• g矩阵（6×6）：用于存储与唯一子序列相关的信息，可能用于计算只出现一次的子序列。
• l和r数组：记录每个字符在区间左端和右端的关联信息，用于合并时判断子序列的唯一性。
• S：位掩码，表示区间中包含的字符集合。

操作流程

1. 初始化：构建线段树，每个叶子节点对应一个字符，初始化其 Info 结构。
2. 更新操作：修改某个位置的字符时，更新对应的叶子节点，并自底向上更新线段树节点，通过重载的 + 运算符合并左右子节点的信息。
3. 查询答案：从根节点获取整体信息，通过 calc 函数计算答案。公式为 sum(f[6][i]) - sum(g[i][j])，可能表示所有非空子序列的出现次数之和减去只出现一次的子序列的出现次数之和，从而得到至少出现两次的不同子序列数量。

复杂度分析

• 构建线段树：O(n log n)
• 每次更新：O(log n)
• 每次查询：O(1)
• 总体复杂度：O((n + q) log n)，适用于 n, q ≤ 50000 的数据规模。