### shakil_AUST's blog

By shakil_AUST, 8 years ago, Can anyone please tell me the process how to solve this problem . Thanx in advance :) dp, Comments (6)
 » Fix two rows and consider all cells between them as an single array... From left to right count for each position the subarrays ending in it, that subarray sum is between A and B, this can be done in for fixed rows (with a binary indexed tree), and overall time ...
•  » » ... which will probably not fit in the time limit. You should remember about two pointers method when you come up with a binary search solution — perhaps it would make the solution faster.
•  » » » you are right, but my pass in time... but i have to recognize than two pointer method is even better...
•  » » can you explain how to use that BIT ? Thanks!
•  » » » we are going to solve the problem with 1D array L = {x1, x2, ..., xn}, let be si = x1 + x2 + ... + xn, and s0 = 0. process L from left to right, if we have an structure that allow us to know how many elements are in range [a, b] when we process xi, if it is the last element in a subarray whose sum is in [a, b], then exists sj(j < i) such that a ≤ si - sj ≤ b, or the same si - b ≤ sj ≤ si - a, then we can add to our solution how many sj are in this range, and add si to the structure for future queries. We can use a treap, but if we process and compress in advance all si, we can use a BIT and the implementation would be easier.
 »