Author: | Pavlo Tsitsei |
Task preparation: | Pavlo Tsitsei |
Editorial: | Pavlo Tsitsei |
Block : a_i is odd for all , n\le 1000: Let's make a prefix sum of the array, so we can find the sum of any subarray in , and then go through all valid intervals. g_{odd} of that interval is not zero if the number of odd elements is odd, i.e., the length of the interval is odd. So, we can just check for each interval if the length is odd and, if so, add its sum to the answer.
Block : n\le 1000: Here, we need to make two additional arrays. Let it be an array and where odd_i=1 if a_i is odd, and otherwise it is 0. For array , even_i=1 if a_i is even, and otherwise it is 0. We can make a prefix sum on this array, and then we need to add g_{odd}(l,r) for some valid interval if the number of such that odd_i is 1 (so the sum of elements on the subarray of array ) is odd, which can be computed using prefix sum. The same goes for even, so we can just traverse all intervals.
Block : a_i is odd for all : Let's fix some element , and we will count how many times it is included in the sum of the interval. As it was stated, a_i is included in g_{odd} if the number of odd elements on the interval is odd, so if the length of the interval is odd, which means that and have different parity. So, we can find it just by counting the number of in the range from to such that it is odd and even, and the same for , but in the range from to .
Block : without additional constraints: Let's generalize the solution for the third block. So, if the element is odd, we need to count the number of intervals where this element is included in g_{odd}, otherwise in g_{even}. We will assume that we include it into g_{odd} always, since for g_{even} it is symmetrical. So, for element it is included in g_{odd}(l, r) if a_i is odd and the interval from to has an odd number of elements. Let's make an array like in the second block, but with the idea from the third. So we fix some , and we need that the parity of odd_r is different from the parity of odd_l. To do this, we can make two new arrays and where we will count the number of even elements of array on the prefix of length and the number of odd such elements, respectively. Now, we can count the number of odd_r which are even or odd using the prefix sum on the array or , and the same for .