题解：分块算法解决区间查询与更新问题

一、题目分析

本题需要处理两种操作：区间更新（对特定范围内元素增加一个值）和区间查询（统计特定范围内大于等于某个值的元素之和）。给定数据规模较大（n 可达 1e6），直接暴力处理会超时，因此需要使用分块算法（块状数组）优化操作效率。

二、核心思路：分块算法

分块算法的核心思想是将数组分成若干个块，对块内元素批量处理，平衡更新和查询的时间复杂度：

1. 分块策略：将长度为 n 的数组分为大小约为 √n 的块（块大小 B = min(n+1, sqrt(n))）。
2. 块内维护：每个块维护排序后的元素、前缀和、懒标记等信息，支持快速批量操作。
3. 操作分类：
   • 对完整块：通过懒标记（tag）记录增量，避免逐元素更新。
   • 对不完整块（边缘部分）：直接遍历元素进行更新或查询。

三、数据结构设计

blk 结构体用于维护单个块的信息：

• 核心数组：
  • a[]：块内元素的原始值。
  • id[]：排序后元素的原始索引（用于映射排序前后的位置）。
  • pos[]：排序后的元素值（方便二分查找）。
  • s[]：排序后元素的前缀和（含块内增量 b[]）。
  • b[]：块内元素的额外增量（处理部分更新）。
  • kk[]：记录每个值在排序数组中的第一个出现位置（用于快速定位阈值）。
• 标记与参数：
  • tag：块的懒标记（整体增量）。
  • h：块内元素数量。

四、关键操作实现

1. 块初始化（init 和 init2）

• 初始化块的数组大小，重置标记和元素值，为后续操作做准备。

2. 完整块更新（add）

• 对整个块增加增量 v，通过更新 tag 实现 O(1) 时间复杂度。

3. 部分块更新（add_partial）

• 对块内 [l, r] 范围的元素增加增量 v：
  • 直接更新 b[] 数组记录部分增量。
  • 同步更新前缀和 s[]（基于排序后的索引，确保查询时能快速累加）。

4. 完整块查询（qry）

• 统计块内大于等于 vr 的元素之和：
  • 通过 kk[vr] 找到排序后第一个大于等于 vr 的元素位置 x。
  • 计算总贡献：(h - x) * tag（懒标记的总贡献）加上前缀和中 [x, h-1] 的和（s[h-1] - (x>0 ? s[x-1] : 0)）。

5. 部分块查询（qry_partial）

• 统计块内 [l, r] 范围中大于等于 vr 的元素之和：
  • 直接遍历范围内元素，累加满足条件的 b[i] + tag（当前元素的实际值增量）。

五、主函数逻辑

1. 输入处理：读取数组和操作，区分更新（op=1）和查询（op=2）操作。
2. 分块遍历：对每个块依次处理：
   • 初始化块内容（当前块的元素范围 [L, R]）。
   • 对块内元素排序，预处理 pos[]、kk[]、s[] 等辅助数组。
   • 遍历所有操作，根据操作范围与当前块的关系，执行完整块或部分块的更新/查询。
3. 输出结果：收集所有查询的结果并输出。

六、时间复杂度分析

• 分块大小：B = O(√n)，总块数 O(n/B) = O(√n)。
• 更新操作：
  • 完整块：O(1) 每块，总 O(√n)。
  • 部分块：O(B) 每块，总 O(B)。
• 查询操作：
  • 完整块：O(1) 每块（依赖预处理的 kk[] 和 s[]），总 O(√n)。
  • 部分块：O(B) 每块，总 O(B)。
• 总体复杂度：单次操作 O(√n)，m 次操作总复杂度 O(m√n)，可满足 n=1e6, m=1e5 级别的数据规模。

七、关键优化点

1. 排序与预处理：块内元素排序后，通过 kk[] 数组快速定位阈值位置，避免每次查询都进行二分查找。
2. 前缀和维护：s[] 数组记录排序后元素的增量前缀和，使完整块查询可直接通过区间和计算。
3. 懒标记与部分增量分离：tag 处理整体增量，b[] 处理部分增量，避免重复更新，减少计算量。

总结

本题通过分块算法将原本 O(n) 复杂度的操作优化为 O(√n)，平衡了更新和查询的效率。核心在于合理划分块大小，以及块内辅助数据结构的设计，使得批量操作和部分操作都能高效执行。分块算法是处理大规模数组区间操作的经典方法，适用于无法用线段树或树状数组高效解决的场景。