Problem Overview:
Name: UVa 12532 - Interval Product
Link: http://uva.onlinejudge.org/external/125/12532.html
Time Limit: 2s
Memory Limit:
My suggested solution:
Difficulty: Medium
Hint: This problem can also be solved by IT algorithm, but BIT is chosen because it's easy and fast to code. Obviously, there are an observation: the result of a product command of all integers between I and J will be zero if at least one of them is zero, it will be positive if the number of negative integers is divisible by 2, and it will be negative otherwise. There are 2 initial binary indexed trees, one stores the number of zeros (zero-tree) and other keeps the number of negative integers (nega-tree). With every integer read from input, the zero-tree should be adjusted by +1 at its position if it is a zero, and if it is a negative integer, the nega-tree should be updated. The changing query can be divided into 2 steps: removing an array element and inserting another element right there. The trees should be updated right after each step. Now, every product command from I to J can be easily calculated by counting the number of zeros and negative integers between I and J based on the observation above.
Complexity: There are K commands, each of which is a change or a product command. The update function and the range sum function can be done in O(logN). So the complexity is O(K * logN)
Algorithm: BIT
Related problem:
My accepted code: