题目理解

这是 BalkanOI 2018 Election 问题的解决方案。题目要求对于每个子串，计算最少删除多少字符，使得每个前缀和每个后缀都满足 C 的数量 ≥ T 的数量。

代码思路解析

1. 问题转化

将问题转化为前缀和模型：

S[i] = S[i-1] + (s[i-1] == 'C' ? 1 : -1);

• C → +1，T → -1
• S[i] 表示前 i 个字符的 C 与 T 的数量差

2. 关键观察

对于子串 S[L..R]，需要满足：

• 每个前缀：S[i] - S[L-1] ≥ 0 对所有 i ∈ [L, R]
• 每个后缀：S[R] - S[j-1] ≥ 0 对所有 j ∈ [L, R]

这等价于：

• 前缀条件：min(S[L..R]) - S[L-1] ≥ 0
• 后缀条件：S[R] - max(S[L-1..R-1]) ≥ 0

3. 线段树设计

struct Node {
    int minv;   // 区间最小值
    int maxv;   // 区间最大值  
    int rise;   // 区间内最大 S[j] - S[i] (i ≤ j)
};

rise 字段是关键，它计算区间内的最大"上升"值。

4. 答案计算

int constantTerm = S[L-1] - S[R];
int ans = constantTerm + got.rise;

其中：

• constantTerm = S[L-1] - S[R] 是基础代价
• got.rise 是区间 [L-1, R] 内的最大上升值
• 最终答案表示需要删除的字符数

算法标签

一级分类：

• 数据结构 ✓

二级分类：

• 线段树 ✓
• 前缀和 ✓
• 区间查询 ✓

其他标签：

• 思维 ✓（问题转化）
• 贪心 ✗

关键技巧

1. 前缀和建模

将字符计数问题转化为数值序列问题

2. 自定义线段树节点

struct Node {
    int minv, maxv, rise;
};

同时维护区间最小值、最大值和最大上升值

3. 合并函数设计

Node mergeNode(const Node &L, const Node &R) {
    return {
        min(L.minv, R.minv),
        max(L.maxv, R.maxv), 
        max({L.rise, R.rise, R.maxv - L.minv})
    };
}

正确合并左右子区间的信息

4. 区间查询优化

使用标准线段树区间查询，时间复杂度 O(log N)

复杂度分析

• 预处理：O(N) 构建前缀和 + O(N) 建线段树
• 每个查询：O(log N)
• 总复杂度：O(N + Q log N)

正确性说明

算法的核心在于：

1. 将字符约束转化为数值约束
2. 通过维护区间最大上升值来捕捉最"不平衡"的部分
3. 结合基础代价计算出需要删除的字符数

总结

这个解法是典型的数据结构优化问题，通过：

1. 问题转化：将字符计数转化为前缀和问题
2. 自定义线段树：设计合适的节点结构和合并函数
3. 高效查询：利用线段树快速回答区间查询

体现了竞赛中问题建模和数据结构设计的重要技巧。