核心思路

主席树 + 贪心选择

问题转化

• 原序列由交替的 $1$ 块和 $0$ 块组成
• $k$-近似序列要求翻转次数 $\leq k$ 时最大化 $1$ 的数量
• 等价于选择一些 $1$ 块，块间用 $0$ 块分隔，总切换次数不超过 $k$

重要公式

1. 切换次数与块选择

选择 $m$ 个 $1$ 块时，切换次数为：

$$\text{切换次数} = 2m - 2 + \delta$$

其中 $\delta$ 取决于首尾块是否为 $1$ 块

2. 最大和计算

对于区间 $[l,r]$，最大和为：

$$\max_{S \subseteq \text{候选1块}} \left\{ \sum_{i \in S} \text{len}_i \right\} $$

满足切换次数约束

3. 贪心策略

• 优先选择长度大的 $1$ 块
• 用主席树维护 $1$ 块长度，支持前 $k$ 大和查询
• 考虑边界情况：区间可能只覆盖块的一部分

算法框架

1. 预处理：

   • 记录每个块的起止位置
   • 对 $1$ 块长度建立主席树（按长度排序）

2. 查询处理：

   • 定位 $l,r$ 所在的块
   • 处理完全包含在单个块内的情况
   • 否则收集边界部分块，枚举边界选择方案
   • 对内部完整 $1$ 块，用主席树查询前 $\lfloor k/2 \rfloor$ 大和

3. 组合答案：

   • 枚举边界块的选择状态
   • 剩余切换次数分配给内部块
   • 取所有情况的最大值

关键优化

• 主席树 $O(\log n)$ 查询前 $k$ 大和
• 边界情况枚举（常数大小）
• 切换次数与选择块数的线性关系