Given a binary string S of 0s and 1s of length N and M queries of the type [l, r],↵
find the number of substrings of S(l to r) where there are even 1s.↵
↵
Constraints:↵
↵
N <= 10^5↵
↵
M <= 10^5↵
↵
1 <= l <= r <= N↵
↵
Sample Input:↵
↵
N = 5↵
↵
S = 10001↵
↵
M = 2↵
↵
2 4↵
↵
3 5↵
↵
↵
Sample Output:↵
↵
6↵
↵
3↵
↵
Explanation:↵
↵
For [2, 4] the 6 valid substrings are [2,2], [2,3], [2,4], [3,3], [3,4], [4,4]↵
↵
For [3, 5] the 3 valid substrings are [3,3], [3,4], [4,4]
find the number of substrings of S(l to r) where there are even 1s.↵
↵
Constraints:↵
↵
N <= 10^5↵
↵
M <= 10^5↵
↵
1 <= l <= r <= N↵
↵
Sample Input:↵
↵
N = 5↵
↵
S = 10001↵
↵
M = 2↵
↵
2 4↵
↵
3 5↵
↵
↵
Sample Output:↵
↵
6↵
↵
3↵
↵
Explanation:↵
↵
For [2, 4] the 6 valid substrings are [2,2], [2,3], [2,4], [3,3], [3,4], [4,4]↵
↵
For [3, 5] the 3 valid substrings are [3,3], [3,4], [4,4]