根号分块：在整块与散块之间折中

问题#

维护一个数组，支持两种操作：

1. 给半开区间 $[l,r)$ 中每个元素加上 $x$；
2. 查询 $[l,r)$ 的元素和。

逐元素修改或查询都可能达到 $O(n)$。分块把数组切成若干连续小块：完整覆盖的块整体 处理，只在区间两端的散块中逐元素处理。

核心思想#

设块长为 $B$。长度为 $n$ 的数组约有 $n/B$ 个块。一次区间操作至多：

• 暴力处理左右两个散块，共 $O(B)$ 个元素；
• 整体处理位于中间的完整块，共 $O(n/B)$ 个。

因此复杂度为：

$$O\left(B+\frac nB\right).$$

取 $B\approx\sqrt n$ 时，两部分达到平衡，复杂度为 $O(\sqrt n)$。

模板对每块维护：

• block_sum[b]：这一块考虑所有标记后的真实元素和；
• lazy[b]：整块每个元素尚未写回原数组的增量；
• values[i]：元素去掉所属块整块标记后的基础值。

不变量#

若位置 $i$ 属于块 $b$，则其真实值始终为：

$$\text{values}[i]+\text{lazy}[b].$$

同时 block_sum[b] 始终等于该块所有真实值之和。整块修改只更新 lazy 与 block_sum；散块修改直接更新元素与块和。

复杂度#

• 建表：$O(n)$
• 区间加：$O(\sqrt n)$
• 区间和：$O(\sqrt n)$
• 空间：$O(n)$

可独立编译的 C++17 模板#

接口与输入统一使用 0-based 半开区间 $[l,r)$。

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

class SqrtDecomposition {
public:
    explicit SqrtDecomposition(const std::vector<long long>& values)
        : size_(values.size()),
          block_size_(
              std::max<std::size_t>(
                  1,
                  static_cast<std::size_t>(
                      std::sqrt(static_cast<double>(size_))
                  ) + 1
              )
          ),
          values_(values),
          block_sum_(
              (size_ + block_size_ - 1) / block_size_,
              0
          ),
          lazy_(block_sum_.size(), 0) {
        for (std::size_t i = 0; i < size_; ++i) {
            block_sum_[block_of(i)] += values_[i];
        }
    }

    std::size_t size() const {
        return size_;
    }

    void range_add(
        std::size_t l,
        std::size_t r,
        long long delta
    ) {
        validate_range(l, r);
        std::size_t current = l;

        while (
            current < r &&
            current % block_size_ != 0
        ) {
            add_one(current, delta);
            ++current;
        }

        while (current + block_size_ <= r) {
            const std::size_t block = block_of(current);
            lazy_[block] += delta;
            block_sum_[block] +=
                delta * static_cast<long long>(block_size_);
            current += block_size_;
        }

        while (current < r) {
            add_one(current, delta);
            ++current;
        }
    }

    long long range_sum(
        std::size_t l,
        std::size_t r
    ) const {
        validate_range(l, r);
        long long answer = 0;
        std::size_t current = l;

        while (
            current < r &&
            current % block_size_ != 0
        ) {
            answer += actual_value(current);
            ++current;
        }

        while (current + block_size_ <= r) {
            answer += block_sum_[block_of(current)];
            current += block_size_;
        }

        while (current < r) {
            answer += actual_value(current);
            ++current;
        }
        return answer;
    }

private:
    std::size_t size_;
    std::size_t block_size_;
    std::vector<long long> values_;
    std::vector<long long> block_sum_;
    std::vector<long long> lazy_;

    std::size_t block_of(std::size_t index) const {
        return index / block_size_;
    }

    long long actual_value(std::size_t index) const {
        return values_[index] + lazy_[block_of(index)];
    }

    void add_one(std::size_t index, long long delta) {
        values_[index] += delta;
        block_sum_[block_of(index)] += delta;
    }

    void validate_range(
        std::size_t l,
        std::size_t r
    ) const {
        if (l > r || r > size_) {
            throw std::out_of_range("invalid range");
        }
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    int operation_count = 0;
    std::cin >> n >> operation_count;
    if (n < 0) {
        return 0;
    }

    std::vector<long long> values(static_cast<std::size_t>(n));
    for (long long& value : values) {
        std::cin >> value;
    }

    SqrtDecomposition blocks(values);
    while (operation_count-- > 0) {
        std::string operation;
        std::size_t l = 0;
        std::size_t r = 0;
        std::cin >> operation >> l >> r;

        if (operation == "add") {
            long long delta = 0;
            std::cin >> delta;
            blocks.range_add(l, r, delta);
        } else if (operation == "sum") {
            std::cout << blocks.range_sum(l, r) << '\n';
        }
    }
}

示例#

输入：

8 4
1 2 3 4 5 6 7 8
sum 0 8
add 2 6 10
sum 1 5
sum 5 8

输出：

36
44
31

修改后数组为 $1,2,13,14,15,16,7,8$。

易错点#

• 最后一块长度不足：不能默认每块都有 $B$ 个元素。模板只有在确实覆盖完整的 $B$ 个位置时才走整块分支。
• 块和语义不统一：要么块和包含 lazy，要么查询时额外计算；不要两种写法混用。
• 散块忘记考虑标记：单个位置的真实值是基础值加所属块 lazy。
• 同块区间重复处理：统一按“左散块—完整块—右散块”推进指针，可自然处理。
• 整数溢出：区间和与 delta * block_length 使用 64 位。
• 块长取 0：空数组也应保证块长至少为 1。

边界测试#

• 空数组上的空区间、单元素数组。
• $n<B$、$n$ 不是完全平方数、最后一个块很短。
• 操作完全位于同一块、恰好覆盖整块、跨一个或多个块。
• $[0,n)$、长度 0、首尾单点。
• 多次整块加后进行散块查询，再交替散块和整块修改。
• 负增量、大数组和大区间，检查 64 位求和。
• 随机生成操作序列，与朴素数组逐元素修改和查询对拍。

常见变体#

单点修改、区间查询#

只需维护原数组与每块聚合值。把 $a_i$ 增加 $\Delta$ 时，同时执行：

$$a_i\mathrel{+}=\Delta,\qquad \text{block\_sum}[\operatorname{block}(i)]\mathrel{+}=\Delta.$$

查询仍拆成左右散块与中间整块。单点修改 $O(1)$，区间查询 $O(\sqrt n)$。

区间修改、单点查询#

完整块只累加 lazy，散块直接修改基础值。单点答案是 values[i] + lazy[block_of(i)]，因此单点查询 $O(1)$，区间修改 $O(\sqrt n)$。

区间修改、区间查询#

这正是正文模板。块和必须在整块与散块修改时同步更新，才能让整块查询保持 $O(1)$。

区间最值#

每块维护最大值或最小值。散块发生任意赋值后，通常需要 $O(B)$ 重建所属块；若是整块 加法，可像正文一样保存 lazy，因为所有元素相对次序不变。

仿射标记：区间乘加与区间和#

在模 $M$ 意义下支持 $x\leftarrow ax+b$ 与区间和。每块保存和以及 lazy $(m,c)$，表示块内基础值尚未写回的变换 $x\mapsto mx+c$。若旧标记是 $g(x)=m_0x+c_0$，新操作是 $f(x)=ax+b$，新标记必须是：

$$f\circ g(x)=(am_0)x+(ac_0+b).$$

因此不能交换乘法和加法标记。散块修改前先 push，整块则直接复合标记并按 $\text{sum}\leftarrow a\cdot\text{sum}+b\cdot\text{len}$ 更新块和。

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

class AffineBlocks {
public:
    static constexpr long long kMod = 1000000007LL;

    explicit AffineBlocks(const std::vector<long long>& input)
        : size_(input.size()),
          block_size_(std::max<std::size_t>(
              1,
              static_cast<std::size_t>(
                  std::sqrt(static_cast<double>(size_))
              ) + 1
          )),
          values_(input),
          block_sum_(block_count(), 0),
          lazy_multiply_(block_count(), 1),
          lazy_add_(block_count(), 0) {
        for (long long& value : values_) {
            value = normalize(value);
        }
        for (std::size_t block = 0; block < block_count(); ++block) {
            rebuild(block);
        }
    }

    void range_affine(
        std::size_t l,
        std::size_t r,
        long long multiply,
        long long add
    ) {
        validate_range(l, r);
        if (l == r) {
            return;
        }
        multiply = normalize(multiply);
        add = normalize(add);

        const std::size_t first = block_of(l);
        const std::size_t last = block_of(r - 1);
        for (std::size_t block = first; block <= last; ++block) {
            const std::size_t left = std::max(l, block_left(block));
            const std::size_t right = std::min(r, block_right(block));
            if (
                left == block_left(block) &&
                right == block_right(block)
            ) {
                apply_block(block, multiply, add);
            } else {
                push(block);
                for (std::size_t i = left; i < right; ++i) {
                    values_[i] = (
                        multiply * values_[i] + add
                    ) % kMod;
                }
                rebuild(block);
            }
        }
    }

    long long range_sum(
        std::size_t l,
        std::size_t r
    ) const {
        validate_range(l, r);
        if (l == r) {
            return 0;
        }

        long long answer = 0;
        const std::size_t first = block_of(l);
        const std::size_t last = block_of(r - 1);
        for (std::size_t block = first; block <= last; ++block) {
            const std::size_t left = std::max(l, block_left(block));
            const std::size_t right = std::min(r, block_right(block));
            if (
                left == block_left(block) &&
                right == block_right(block)
            ) {
                answer = (answer + block_sum_[block]) % kMod;
            } else {
                for (std::size_t i = left; i < right; ++i) {
                    answer = (answer + actual_value(i)) % kMod;
                }
            }
        }
        return answer;
    }

private:
    std::size_t size_;
    std::size_t block_size_;
    std::vector<long long> values_;
    std::vector<long long> block_sum_;
    std::vector<long long> lazy_multiply_;
    std::vector<long long> lazy_add_;

    static long long normalize(long long value) {
        value %= kMod;
        if (value < 0) {
            value += kMod;
        }
        return value;
    }

    std::size_t block_count() const {
        return (size_ + block_size_ - 1) / block_size_;
    }

    std::size_t block_of(std::size_t index) const {
        return index / block_size_;
    }

    std::size_t block_left(std::size_t block) const {
        return block * block_size_;
    }

    std::size_t block_right(std::size_t block) const {
        return std::min(size_, block_left(block) + block_size_);
    }

    long long actual_value(std::size_t index) const {
        const std::size_t block = block_of(index);
        return (
            lazy_multiply_[block] * values_[index] +
            lazy_add_[block]
        ) % kMod;
    }

    void rebuild(std::size_t block) {
        block_sum_[block] = 0;
        for (
            std::size_t i = block_left(block);
            i < block_right(block);
            ++i
        ) {
            block_sum_[block] =
                (block_sum_[block] + values_[i]) % kMod;
        }
    }

    void push(std::size_t block) {
        if (
            lazy_multiply_[block] == 1 &&
            lazy_add_[block] == 0
        ) {
            return;
        }
        for (
            std::size_t i = block_left(block);
            i < block_right(block);
            ++i
        ) {
            values_[i] = actual_value(i);
        }
        lazy_multiply_[block] = 1;
        lazy_add_[block] = 0;
    }

    void apply_block(
        std::size_t block,
        long long multiply,
        long long add
    ) {
        const long long length = static_cast<long long>(
            block_right(block) - block_left(block)
        );
        block_sum_[block] = (
            multiply * block_sum_[block] + add * length
        ) % kMod;
        lazy_multiply_[block] =
            multiply * lazy_multiply_[block] % kMod;
        lazy_add_[block] = (
            multiply * lazy_add_[block] + add
        ) % kMod;
    }

    void validate_range(
        std::size_t l,
        std::size_t r
    ) const {
        if (l > r || r > size_) {
            throw std::out_of_range("invalid range");
        }
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    int operation_count = 0;
    std::cin >> n >> operation_count;
    if (n < 0 || operation_count < 0) {
        return 0;
    }

    std::vector<long long> values(static_cast<std::size_t>(n));
    for (long long& value : values) {
        std::cin >> value;
    }

    AffineBlocks blocks(values);
    while (operation_count-- > 0) {
        std::string operation;
        std::size_t l = 0;
        std::size_t r = 0;
        std::cin >> operation >> l >> r;
        if (operation == "affine") {
            long long multiply = 0;
            long long add = 0;
            std::cin >> multiply >> add;
            blocks.range_affine(l, r, multiply, add);
        } else if (operation == "sum") {
            std::cout << blocks.range_sum(l, r) << '\n';
        }
    }
}

区间赋值与区间计数#

支持把 $[l,r)$ 全部赋成 $x$，并询问 $[l,r)$ 中等于 $x$ 的元素个数。每块维护频次表； 整块赋值时清空频次表，只保留“新值 $\to$ 块长”，并记录覆盖标记。散块修改前把覆盖 标记写回元素，再重建该块。使用哈希表时，复杂度中的查找为期望 $O(1)$。

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <optional>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <vector>

class AssignmentCountBlocks {
public:
    explicit AssignmentCountBlocks(
        const std::vector<long long>& values
    )
        : size_(values.size()),
          block_size_(std::max<std::size_t>(
              1,
              static_cast<std::size_t>(
                  std::sqrt(static_cast<double>(size_))
              ) + 1
          )),
          values_(values),
          assigned_(block_count()),
          frequency_(block_count()) {
        for (std::size_t block = 0; block < block_count(); ++block) {
            rebuild(block);
        }
    }

    void range_assign(
        std::size_t l,
        std::size_t r,
        long long value
    ) {
        validate_range(l, r);
        if (l == r) {
            return;
        }

        const std::size_t first = block_of(l);
        const std::size_t last = block_of(r - 1);
        for (std::size_t block = first; block <= last; ++block) {
            const std::size_t left = std::max(l, block_left(block));
            const std::size_t right = std::min(r, block_right(block));
            if (
                left == block_left(block) &&
                right == block_right(block)
            ) {
                apply_assignment(block, value);
            } else {
                push(block);
                std::fill(
                    values_.begin() +
                        static_cast<std::ptrdiff_t>(left),
                    values_.begin() +
                        static_cast<std::ptrdiff_t>(right),
                    value
                );
                rebuild(block);
            }
        }
    }

    std::size_t range_count(
        std::size_t l,
        std::size_t r,
        long long value
    ) const {
        validate_range(l, r);
        if (l == r) {
            return 0;
        }

        std::size_t answer = 0;
        const std::size_t first = block_of(l);
        const std::size_t last = block_of(r - 1);
        for (std::size_t block = first; block <= last; ++block) {
            const std::size_t left = std::max(l, block_left(block));
            const std::size_t right = std::min(r, block_right(block));
            if (
                left == block_left(block) &&
                right == block_right(block)
            ) {
                const auto found = frequency_[block].find(value);
                if (found != frequency_[block].end()) {
                    answer += found->second;
                }
            } else {
                for (std::size_t i = left; i < right; ++i) {
                    if (actual_value(i) == value) {
                        ++answer;
                    }
                }
            }
        }
        return answer;
    }

private:
    std::size_t size_;
    std::size_t block_size_;
    std::vector<long long> values_;
    std::vector<std::optional<long long>> assigned_;
    std::vector<std::unordered_map<long long, std::size_t>> frequency_;

    std::size_t block_count() const {
        return (size_ + block_size_ - 1) / block_size_;
    }

    std::size_t block_of(std::size_t index) const {
        return index / block_size_;
    }

    std::size_t block_left(std::size_t block) const {
        return block * block_size_;
    }

    std::size_t block_right(std::size_t block) const {
        return std::min(size_, block_left(block) + block_size_);
    }

    long long actual_value(std::size_t index) const {
        const std::size_t block = block_of(index);
        return assigned_[block].has_value()
            ? *assigned_[block]
            : values_[index];
    }

    void rebuild(std::size_t block) {
        frequency_[block].clear();
        for (
            std::size_t i = block_left(block);
            i < block_right(block);
            ++i
        ) {
            ++frequency_[block][values_[i]];
        }
    }

    void push(std::size_t block) {
        if (!assigned_[block].has_value()) {
            return;
        }
        std::fill(
            values_.begin() + static_cast<std::ptrdiff_t>(
                block_left(block)
            ),
            values_.begin() + static_cast<std::ptrdiff_t>(
                block_right(block)
            ),
            *assigned_[block]
        );
        assigned_[block].reset();
    }

    void apply_assignment(std::size_t block, long long value) {
        assigned_[block] = value;
        frequency_[block].clear();
        frequency_[block][value] =
            block_right(block) - block_left(block);
    }

    void validate_range(
        std::size_t l,
        std::size_t r
    ) const {
        if (l > r || r > size_) {
            throw std::out_of_range("invalid range");
        }
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    int operation_count = 0;
    std::cin >> n >> operation_count;
    if (n < 0 || operation_count < 0) {
        return 0;
    }

    std::vector<long long> values(static_cast<std::size_t>(n));
    for (long long& value : values) {
        std::cin >> value;
    }

    AssignmentCountBlocks blocks(values);
    while (operation_count-- > 0) {
        std::string operation;
        std::size_t l = 0;
        std::size_t r = 0;
        long long value = 0;
        std::cin >> operation >> l >> r >> value;
        if (operation == "assign") {
            blocks.range_assign(l, r, value);
        } else if (operation == "count") {
            std::cout << blocks.range_count(l, r, value) << '\n';
        }
    }
}

区间开方与区间和#

这一模型要求元素非负，修改为 $a_i\leftarrow\lfloor\sqrt{a_i}\rfloor$。它不能像加法 那样合并成简单 lazy，但有“值很快稳定”的性质：0 和 1 再开方都不变。每块维护和与 最大值；若一个完整块的最大值不超过 1，就能整块跳过，否则扫描并重建。

单次修改的严格最坏复杂度仍可能是 $O(n)$，不能误写成 $O(\sqrt n)$；优势来自每个值在 有限次开方后都会稳定，以及稳定整块之后只需 $O(1)$ 检查。模板用修正后的浮点初值计算 精确整数平方根，避免大整数在平方比较时溢出。

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

class SquareRootBlocks {
public:
    explicit SquareRootBlocks(const std::vector<long long>& values)
        : size_(values.size()),
          block_size_(std::max<std::size_t>(
              1,
              static_cast<std::size_t>(
                  std::sqrt(static_cast<double>(size_))
              ) + 1
          )),
          values_(values),
          block_sum_(block_count(), 0),
          block_maximum_(block_count(), 0) {
        for (long long value : values_) {
            if (value < 0) {
                throw std::invalid_argument("square root needs nonnegative values");
            }
        }
        for (std::size_t block = 0; block < block_count(); ++block) {
            rebuild(block);
        }
    }

    void range_square_root(std::size_t l, std::size_t r) {
        validate_range(l, r);
        if (l == r) {
            return;
        }

        const std::size_t first = block_of(l);
        const std::size_t last = block_of(r - 1);
        for (std::size_t block = first; block <= last; ++block) {
            const std::size_t left = std::max(l, block_left(block));
            const std::size_t right = std::min(r, block_right(block));
            if (
                left == block_left(block) &&
                right == block_right(block) &&
                block_maximum_[block] <= 1
            ) {
                continue;
            }
            for (std::size_t i = left; i < right; ++i) {
                values_[i] = integer_square_root(values_[i]);
            }
            rebuild(block);
        }
    }

    long long range_sum(
        std::size_t l,
        std::size_t r
    ) const {
        validate_range(l, r);
        if (l == r) {
            return 0;
        }

        long long answer = 0;
        const std::size_t first = block_of(l);
        const std::size_t last = block_of(r - 1);
        for (std::size_t block = first; block <= last; ++block) {
            const std::size_t left = std::max(l, block_left(block));
            const std::size_t right = std::min(r, block_right(block));
            if (
                left == block_left(block) &&
                right == block_right(block)
            ) {
                answer += block_sum_[block];
            } else {
                for (std::size_t i = left; i < right; ++i) {
                    answer += values_[i];
                }
            }
        }
        return answer;
    }

private:
    std::size_t size_;
    std::size_t block_size_;
    std::vector<long long> values_;
    std::vector<long long> block_sum_;
    std::vector<long long> block_maximum_;

    static long long integer_square_root(long long value) {
        long long root = static_cast<long long>(
            std::sqrt(static_cast<long double>(value))
        );
        while (root + 1 <= value / (root + 1)) {
            ++root;
        }
        while (root > 0 && root > value / root) {
            --root;
        }
        return root;
    }

    std::size_t block_count() const {
        return (size_ + block_size_ - 1) / block_size_;
    }

    std::size_t block_of(std::size_t index) const {
        return index / block_size_;
    }

    std::size_t block_left(std::size_t block) const {
        return block * block_size_;
    }

    std::size_t block_right(std::size_t block) const {
        return std::min(size_, block_left(block) + block_size_);
    }

    void rebuild(std::size_t block) {
        block_sum_[block] = 0;
        block_maximum_[block] = 0;
        for (
            std::size_t i = block_left(block);
            i < block_right(block);
            ++i
        ) {
            block_sum_[block] += values_[i];
            block_maximum_[block] =
                std::max(block_maximum_[block], values_[i]);
        }
    }

    void validate_range(
        std::size_t l,
        std::size_t r
    ) const {
        if (l > r || r > size_) {
            throw std::out_of_range("invalid range");
        }
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    int operation_count = 0;
    std::cin >> n >> operation_count;
    if (n < 0 || operation_count < 0) {
        return 0;
    }

    std::vector<long long> values(static_cast<std::size_t>(n));
    for (long long& value : values) {
        std::cin >> value;
    }

    SquareRootBlocks blocks(values);
    while (operation_count-- > 0) {
        std::string operation;
        std::size_t l = 0;
        std::size_t r = 0;
        std::cin >> operation >> l >> r;
        if (operation == "sqrt") {
            blocks.range_square_root(l, r);
        } else if (operation == "sum") {
            std::cout << blocks.range_sum(l, r) << '\n';
        }
    }
}

块内排序查询：区间加与计数#

支持区间加，以及询问 $[l,r)$ 中小于等于 $x$ 的元素个数。每块保存基础值的有序副本 和整块加标记。完整块查询时，在有序副本中二分 upper_bound(x - lazy)；散块直接检查 values[i] + lazy[block]。散块修改后只重排受影响的块。

取 $B\approx\sqrt n$ 时，修改为 $O(B\log B+n/B)$，查询为 $O(B+(n/B)\log B)$。模板假定所有加法及 x - lazy 都在 64 位有符号整数 范围内。

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

class SortedBlocks {
public:
    explicit SortedBlocks(const std::vector<long long>& values)
        : size_(values.size()),
          block_size_(std::max<std::size_t>(
              1,
              static_cast<std::size_t>(
                  std::sqrt(static_cast<double>(size_))
              ) + 1
          )),
          values_(values),
          sorted_(block_count()),
          lazy_add_(block_count(), 0) {
        for (std::size_t block = 0; block < block_count(); ++block) {
            rebuild(block);
        }
    }

    void range_add(
        std::size_t l,
        std::size_t r,
        long long delta
    ) {
        validate_range(l, r);
        if (l == r) {
            return;
        }

        const std::size_t first = block_of(l);
        const std::size_t last = block_of(r - 1);
        for (std::size_t block = first; block <= last; ++block) {
            const std::size_t left = std::max(l, block_left(block));
            const std::size_t right = std::min(r, block_right(block));
            if (
                left == block_left(block) &&
                right == block_right(block)
            ) {
                lazy_add_[block] += delta;
            } else {
                for (std::size_t i = left; i < right; ++i) {
                    values_[i] += delta;
                }
                rebuild(block);
            }
        }
    }

    std::size_t range_count_at_most(
        std::size_t l,
        std::size_t r,
        long long limit
    ) const {
        validate_range(l, r);
        if (l == r) {
            return 0;
        }

        std::size_t answer = 0;
        const std::size_t first = block_of(l);
        const std::size_t last = block_of(r - 1);
        for (std::size_t block = first; block <= last; ++block) {
            const std::size_t left = std::max(l, block_left(block));
            const std::size_t right = std::min(r, block_right(block));
            if (
                left == block_left(block) &&
                right == block_right(block)
            ) {
                const long long base_limit = limit - lazy_add_[block];
                answer += static_cast<std::size_t>(
                    std::upper_bound(
                        sorted_[block].begin(),
                        sorted_[block].end(),
                        base_limit
                    ) - sorted_[block].begin()
                );
            } else {
                for (std::size_t i = left; i < right; ++i) {
                    if (values_[i] + lazy_add_[block] <= limit) {
                        ++answer;
                    }
                }
            }
        }
        return answer;
    }

private:
    std::size_t size_;
    std::size_t block_size_;
    std::vector<long long> values_;
    std::vector<std::vector<long long>> sorted_;
    std::vector<long long> lazy_add_;

    std::size_t block_count() const {
        return (size_ + block_size_ - 1) / block_size_;
    }

    std::size_t block_of(std::size_t index) const {
        return index / block_size_;
    }

    std::size_t block_left(std::size_t block) const {
        return block * block_size_;
    }

    std::size_t block_right(std::size_t block) const {
        return std::min(size_, block_left(block) + block_size_);
    }

    void rebuild(std::size_t block) {
        sorted_[block].assign(
            values_.begin() + static_cast<std::ptrdiff_t>(
                block_left(block)
            ),
            values_.begin() + static_cast<std::ptrdiff_t>(
                block_right(block)
            )
        );
        std::sort(sorted_[block].begin(), sorted_[block].end());
    }

    void validate_range(
        std::size_t l,
        std::size_t r
    ) const {
        if (l > r || r > size_) {
            throw std::out_of_range("invalid range");
        }
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    int operation_count = 0;
    std::cin >> n >> operation_count;
    if (n < 0 || operation_count < 0) {
        return 0;
    }

    std::vector<long long> values(static_cast<std::size_t>(n));
    for (long long& value : values) {
        std::cin >> value;
    }

    SortedBlocks blocks(values);
    while (operation_count-- > 0) {
        std::string operation;
        std::size_t l = 0;
        std::size_t r = 0;
        long long value = 0;
        std::cin >> operation >> l >> r >> value;
        if (operation == "add") {
            blocks.range_add(l, r, value);
        } else if (operation == "count") {
            std::cout << blocks.range_count_at_most(l, r, value)
                      << '\n';
        }
    }
}

延伸阅读（非课程主线）：莫队算法#

当数组静态、询问可以离线，且加入/删除一个端点能快速维护答案时，可以按左右端点分块 排序，将总移动次数控制在约 $O((n+q)\sqrt n)$。它与这里的在线分块不是同一个模板。