官方题解｜统计区间内奇数与偶数的数量

题目解析

对于每个查询，若直接使用循环暴力统计 $[L_i, R_i]$ 内的奇数或偶数，时间复杂度为 $\mathrm{O}(R_i - L_i)$。本题 $1 \le L_i \le R_i \le 10^9$。暴力统计会超出时间限制。

我们不妨思考一个问题：给定任意正整数 $N$，求 $[1, N]$ 中所有「奇数」的数量，如何解决这个问题？
不妨枚举，打表找找规律，$1, 3, 5, 7, 9, 11, \cdots$。
分类讨论一下：

1. 当 $N$ 为「奇数」时，那么显然一共有 $\frac{N + 1}{2}$ 个「奇数」；
2. 当 $N$ 为「偶数」时，那么显然一共有 $\frac{N}{2}$ 个「奇数」；
3. 由于 C++ 中整数做除法自动抹除小数，所以可以统一写成 $\frac{N + 1}{2}$。

那么我可以考虑使用「前缀和」的思想，计算出 $[1, L_i - 1]$ 中「奇数」的数量 $odd(L_i - 1)$ 和 $[1, R_i]$ 中「奇数」的数量 $odd(R_i)$，那么 $[L_i, R_i]$ 中「奇数」的数量为 $odd(R_i) - odd(L_i - 1)$。

统计「偶数」的数量同理。

AC代码

C++ 代码：

#include <bits/stdc++.h>

int main() {
    int _; std::cin >> _;
    while (_--) {
        int t, l, r;
        std::cin >> t >> l >> r;
        auto odd = [](int x) {return x + 1 >> 1;};
        auto even = [](int x) {return x >> 1;};
        std:: cout << (t == 1 ? odd(r) - odd(l-1) : even(r) - even(l-1)) << '\n';
    }
    return 0;
}

Python 代码：

for _ in range(int(input())):
    t, l, r = map(int, input().split())
    odd = lambda x: x + 1 >> 1
    even = lambda x: x >> 1
    print(odd(r) - odd(l-1) if t == 1 else even(r) - even(l-1))