题目分析

本题要求实现两种操作：

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

区间查询：查询区间 $[l, r]$ 内小于 $c^2$ 的元素个数

数据规模为 $n \leq 50000$，直接暴力处理会超时，因此需要使用分块算法。

算法思路

分块思想 将数组分成 $\sqrt{n}$ 个块，每个块的大小约为 $\sqrt{n}$。对于每个块，我们维护：

原始数组 a[]

排序后的数组 b[]（用于二分查找）

懒标记 lz[]（记录整个块的增量）

关键操作

1.初始化建块 (build 函数) 计算块大小 $B = \sqrt{n}$ 和块数 $m$

为每个位置分配块编号 idx[i]

记录每个块的左右边界 L[i] 和 R[i]

对每个块内的元素进行排序，存入 b[] 数组

2.区间更新 (update 函数) 情况1：区间完全在一个块内

直接暴力更新 a[] 数组

重新构建该块的排序数组 b[]

情况2：区间跨越多个块

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

处理中间完整块：只更新懒标记 lz[]（不修改数组）

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

3. 区间查询 (query 函数) 情况1：区间完全在一个块内

暴力遍历，统计满足 a[i] + lz[sid] < k 的元素个数

情况2：区间跨越多个块

处理左不完整块：暴力统计

处理中间完整块：在排序数组 b[] 上二分查找满足条件的元素个数

处理右不完整块：暴力统计

时间复杂度

建块：$O(n \log \sqrt{n})$

更新操作：$O(\sqrt{n} + \sqrt{n} \log \sqrt{n})$

查询操作：$O(\sqrt{n} + \sqrt{n} \log \sqrt{n})$

总体复杂度为 $O(n \sqrt{n} \log \sqrt{n})$，对于 $n = 50000$ 可以接受。

代码实现要点

1.块的管理 ll B = sqrt(n), m = (n + B - 1) / B; for (ll i = 1; i <= n; i++) idx[i] = (i - 1) / B + 1; 2. 二分查找优化 在完整块中查询时，利用排序后的数组进行二分查找： ll LL = L[i], RR = R[i], pos = 0; while (LL <= RR) { ll mid = (LL + RR) >> 1; if (b[mid] + lz[i] < k) LL = mid + 1, pos = mid; else RR = mid - 1; } if (pos) ans += pos - L[i] + 1; 3.懒标记应用 更新完整块时只更新懒标记，查询时再将懒标记考虑进去： // 更新时 lz[i] += k;

// 查询时
a[i] + lz[sid] < k // 不完整块 b[mid] + lz[i] < k // 完整块二分

代码总结

本题展示了分块算法的典型应用：

将大规模问题分解为小块处理

通过排序和二分优化查询

使用懒标记减少不必要的更新操作

分块算法在 $O(n \sqrt{n})$ 复杂度级别的问题中非常实用，是介于暴力和高级数据结构之间的折中方案。