Let the original array be A[N] and the final array be C[N].
(1) If 2K+1 >= N, then C = bitwise AND of all elements of A, for all i.
(2) Otherwise, C* = bitwise AND of 2*K+1 elements of A (centered at index i) i.e.
C* = bitwise AND of (A[i-K], A[i-K+1],…,A[i-1], A*, A[i+1],…, A[i+K-1], A[i+K]) where the indexes are circular.
To implement this, I have constructed another array B to handle the circularity.
Let B = A’+A+A, where A’ = reverse of A. Now, I have used a segment tree built on top of array B to compute the bitwise AND of a range of elements.
I am getting Wrong Answer. Is there anything fundamentally wrong in this approach?
Here is my code - http://www.codechef.com/viewsolution/3062954