第二题 - 统计区间内奇数与偶数的数量 题目链接跳转：点击跳转 对于这种区间的问题，可以先考虑一部分。如果要求出从 [1,L][1, L][1,L] 区间内满足条件的数字我们应该怎么办？假设 LLL 是一个偶数，那么 [1,L][1, L][1,L] 区间的奇数和偶数就应该是 L/2L / 2L/2。相同地，假设 LLL 是一个奇数，那么 [1,L][1, L][1,L] 区间的奇数和偶数就分别是 L/2+1L / 2 + 1L/2+1 和 L/2L / 2L/2。注意到 L/2+1L / 2 + 1L/2+1 和 L/2L / 2L/2 两个公式都可以被简写成 (L+1)/2(L + 1) / 2(L+1)/2。 设 odd(L)odd(L)odd(L) 和 even(L)even(L)even(L) 分别为区间 [1,L][1, L][1,L] 的奇数个数和偶数个数。那么可以得出结论，如果要求 [L,R][L, R][L,R] 区间的奇数个数，答案就应该是 odd(R)−odd(L−1)odd(R) - odd(L-1)odd(R)−odd(L−1) 和 even(R)−even(L−1)even(R) - even(L-1)even(R)−even(L−1)。 本题的 AC 代码如下，代码并没有使用函数，见谅：

题目解析 对于每个查询，若直接使用循环暴力统计 [Li,Ri][L_i, R_i][Li ,Ri ] 内的奇数或偶数，时间复杂度为 O(Ri−Li)\mathrm{O}(R_i - L_i)O(Ri −Li )。本题 1≤Li≤Ri≤1091 \le L_i \le R_i \le 10^91≤Li ≤Ri ≤109。暴力统计会超出时间限制。 我们不妨思考一个问题：给定任意正整数 NNN，求 [1,N][1, N][1,N] 中所有「奇数」的数量，如何解决这个问题？ 不妨枚举，打表找找规律，1,3,5,7,9,11,⋯1, 3, 5, 7, 9, 11, \cdots1,3,5,7,9,11,⋯。 分类讨论一下： 1. 当 NNN 为「奇数」时，那么显然一共有 N+12\frac{N + 1}{2}2N+1 个「奇数」； 2. 当 NNN 为「偶数」时，那么显然一共有 N2\frac{N}{2}2N 个「奇数」； 3. 由于 C++ 中整数做除法自动抹除小数，所以可以统一写成 N+12\frac{N + 1}{2}2N+1 。 那么我可以考虑使用「前缀和」的思想，计算出 [1,Li−1][1, L_i - 1][1,Li −1] 中「奇数」的数量 odd(Li−1)odd(L_i - 1)odd(Li −1) 和 [1,Ri][1, R_i][1,Ri ] 中「奇数」的数量 odd(Ri)odd(R_i)odd(Ri )，那么 [Li,Ri][L_i, R_i][Li ,Ri ] 中「奇数」的数量为 odd(Ri)−odd(Li−1)odd(R_i) - odd(L_i - 1)odd(Ri )−odd(Li −1)。 统计「偶数」的数量同理。 AC代码 C++ 代码： Python 代码：

> > > 找到规律就能写出来了

SOL 1 对于 Li,RiL_i,R_iLi ,Ri 较小的情况，我们可以用暴力枚举的方式。即，对于 Li∼RiL_i\sim R_iLi ∼Ri 内的每一个数，判断是奇数还是偶数，并数一下一共有几个。 时间复杂度 O(qA)O(qA)O(qA)，其中 A=max⁡Ri−LiA=\max R_i-L_iA=maxRi −Li 。 期望得分 505050 分。 SOL 2 对于 Li,RiL_i,R_iLi ,Ri 中等的情况，我们可以用前缀和。即，设 f1,if_{1,i}f1,i 表示 1∼i1\sim i1∼i 中有几个奇数，f2,if_{2,i}f2,i 表示 1∼i1\sim i1∼i 中有几个偶数。求 l∼rl\sim rl∼r 内有几个奇数/偶数，可以用前缀和相减去求，即答案为 fTi,Ri−fTi,Li−1f_{T_i,R_i}-f_{T_i,L_i-1}fTi ,Ri −fTi ,Li −1 。 时间复杂度 O(A+q)O(A+q)O(A+q)，空间复杂度 O(A)O(A)O(A)，AAA 与上文同理。 期望得分 505050 分。 SOL 3 考虑到是连续区间，想想有没有数学解法。 * Case 1，l,rl,rl,r 同奇偶。 这时候 r−l+1r-l+1r−l+1 是一个偶数，也就是与 l,rl,rl,r 奇偶性相同的那种数会多 111 个。 假设 l,rl,rl,r 均为奇数，则奇数会有 r−l2+1\frac{r-l}2+12r−l +1 个，偶数有 r−l2\frac{r-l}{2}2r−l 个。均为偶数同理。 你可以自己手酸找找规律。 * Case 2，l,rl,rl,r 不同奇偶 这时候奇偶个数一样，都是 r−l+12\frac{r-l+1}22r−l+1 个。 将上述过程实现即可，单次询问是 O(1)O(1)O(1) 的，总复杂度 O(q)O(q)O(q)。可以采用位运算优化常数，尽管没用。