解题思路与算法

前缀和+奇偶性计数

令原数组为 $a[1\ldots n]$，定义前缀和数组 $S[0]=0,$$\quad S[i]=\sum_{k=1}^i$$a[k]\quad(1\le i\le n).$ 子数组 $a[i\ldots j]$ 的和为 $S[j]-S[i-1]$，当且仅当 $S[j]$ 与 $S[i-1]$ 奇偶性不同时，该子数组和为奇数。

对于一次查询区间 $[l,r]$，我们要统计所有 $(i,j)$，满足 $l\le i\le j\le r,\quad S[j]-S[i-1]\equiv1\pmod2.$

题目内容

有一个数组，长度为$n$，记作{$a_1,a_2,...,a_n$}.

小$O$想知道，在区间$[l,r]$上，有多少个子数组使得所有元素之和为奇数。

[名词解释]

• 子数组为从原数组中，连续地选择一段元素(可以全选、可以不选)得到的新数组。

输入描述

第一行输入两个整数$n,q(1≦n,q≦2×10^5)$,分别表示数阵的长度与查询次数。

第二行输入$n$个整数$a_1，a_2,...,a_n (1≦a_i≦10^9)$,表示数阵元累。

接下来$q$行，每行输入两个整数$l$和$r(1≦l≦r≦n)$,表示询问区间.

输出描述

对于每次询问，在一行上输出一个整数，表示区间$[l,r]$内所有子数组之和为奇数的数量。

样例1

输入

5 3
1 2 3 4 5
1 5 
3 3
2 2

输出

9
1 
0

说明

在第一个样例中，数阵为{$1, 2, 3, 4, 5$}。

• 对区间$[1,5]$，共有$9$个了数组的和为奇数:长度为$1$的子数组有$[1,1],[3,3],[5,5]$,长度为$2$的子数组有 $[1, 2], [2, 3], [3, 4], [4,5]$,长度为$3$的子数组有$[2,3,4]$，长度为$5$的子数组有$[1,2,3,4,5]$，一共有$3+4+1+1=9$个;
• 对区间$[3,3]$，子数组{$3$}的和为奇数，共$1$个;
• 对区间$[2,2]$，子数组{$2$}的和为偶数，共$0$个。

样例2

输入

3 2
2 3 2
1 3
2 3

输出

4
2