验题人题解|统计区间内奇数与偶数的数量

Sol 1

对于 $L_i,R_i$ 较小的情况，我们可以用暴力枚举的方式。即，对于 $L_i\sim R_i$ 内的每一个数，判断是奇数还是偶数，并数一下一共有几个。

时间复杂度 $O(qA)$，其中 $A=\max R_i-L_i$。

期望得分 $50$ 分。

Sol 2

对于 $L_i,R_i$ 中等的情况，我们可以用前缀和。即，设 $f_{1,i}$ 表示 $1\sim i$ 中有几个奇数，$f_{2,i}$ 表示 $1\sim i$ 中有几个偶数。求 $l\sim r$ 内有几个奇数/偶数，可以用前缀和相减去求，即答案为 $f_{T_i,R_i}-f_{T_i,L_i-1}$。

时间复杂度 $O(A+q)$，空间复杂度 $O(A)$，$A$ 与上文同理。

期望得分 $50$ 分。

Sol 3

考虑到是连续区间，想想有没有数学解法。

• Case 1，$l,r$ 同奇偶。

  这时候 $r-l+1$ 是一个偶数，也就是与 $l,r$ 奇偶性相同的那种数会多 $1$ 个。

  假设 $l,r$ 均为奇数，则奇数会有 $\frac{r-l}2+1$ 个，偶数有 $\frac{r-l}{2}$ 个。均为偶数同理。

  你可以自己手酸找找规律。

• Case 2，$l,r$ 不同奇偶

  这时候奇偶个数一样，都是 $\frac{r-l+1}2$ 个。

将上述过程实现即可，单次询问是 $O(1)$ 的，总复杂度 $O(q)$。可以采用位运算优化常数，尽管没用。

void solve(){
	ll opt,l,r;
	cin>>opt>>l>>r;
	ll cnt1=(r-l+1)/2;
	if((r-l)&1){
		cout<<cnt1<<endl; 
	}
	else{
		if((opt&1)==(l&1)) cout<<cnt1+1<<endl;
		else cout<<cnt1<<endl;
	}
}