题目分析

给定一个长度为 $n$ 的数列，需要进行 $n$ 次操作，操作分为两种类型：

区间加法：将区间 $[l, r]$ 内的所有数加上 $c$

区间前驱查询：在区间 $[l, r]$ 内找到小于 $c$ 的最大元素（即前驱），如果不存在则输出 $-1$

解题思路

本题采用分块算法解决，将数组分成多个块，每个块维护排序后的数据，以平衡暴力操作和高效查询。 分块设计 块大小 $B$ 设为 $\sqrt{n}$ 左右（代码中固定为 500）

每个块维护：

原始数据（数组 $a$）

排序后的数据（数组 $b$）

懒标记 $lz$（用于区间加法优化）

关键操作

1.初始化建块 计算每个元素的块编号

确定每个块的左右边界

将每个块内的数据排序存储

2.区间更新 同一块内：直接暴力更新并重新排序

跨多个块：

左右不完整块：暴力更新并重新排序

中间完整块：仅更新懒标记，不修改实际数据

3.前驱查询 同一块内：遍历所有元素，加上懒标记后比较

跨多个块：

左右不完整块：暴力遍历

中间完整块：在排序数组中使用二分查找

算法优势

懒标记优化：完整块的区间加法只需更新懒标记，避免频繁排序

二分查找：利用排序后的块内数据快速查找前驱

平衡复杂度：在暴力与高效算法间取得平衡 复杂度分析 建块：$O(n \log \sqrt{n})$

单次更新：$O(\sqrt{n} \log \sqrt{n})$

单次查询：$O(\sqrt{n} \log \sqrt{n})$

总复杂度：$O(n \sqrt{n} \log \sqrt{n})$，对于 $n=10^5$ 可接受

关键点说明

懒标记应用：完整块的区间加法只更新懒标记，查询时再考虑，大幅减少排序次数

二分查找优化：在排序后的块内数据中快速定位前驱

边界处理：仔细处理块边界情况，确保不遗漏任何元素

初始化技巧：通过预计算块边界和排序，为后续操作打好基础

代码总结

本题展示了分块算法在处理复杂区间操作时的强大能力，通过合理的块大小选择和操作优化，在保证正确性的同时获得了较好的时间复杂度。这种思想可以推广到其他类似的区间操作问题中。