解题思路与算法

前缀和+奇偶性计数

令序列为 $b[1\ldots n]$。对于每个位置 $i$，定义 $x_i = b_i \bmod 2$（$x_i = 1$ 表示该位置是活跃点，$x_i = 0$ 表示平静点）。定义前缀和数组
$S[0]=0,\quad S[i]=\sum_{k=1}^i x_k \quad(1\le i\le n),$
即 $S[i]$ 表示前 $i$ 个位置中活跃点的总个数。子段 $b[i\ldots j]$ 中包含的活跃点个数为 $S[j]-S[i-1]$，当且仅当 $S[j]$ 与 $S[i-1]$ 奇偶性不同时，该子段活跃点个数为奇数，即该子段是一个脉冲子段。

对于一次查询区间 $[l,r]$，我们要统计所有满足条件的子段 $(i,j)$，满足