ANDROUND question

problem-http://www.spoj.com/problems/ANDROUND/
Can someone please help provide a detailed solution on the above problem, am not able to understand why and how to apply segment tree in the given problem.Please Help

3 Likes

Think of a particular element A[i]. After 1 round it becomes A[i-1] & A[i] & A[i+1]. After 2 rounds it becomes (A[i-2] & A[i-1] & A[i]) & (A[i-1] & A[i] & A[i+1]) & (A[i] & A[i+1] & A[i+2]) which simplifies to A[i-2] & A[i-1] & A[i] & A[i+1] & A[i+2]. So you can see that after K rounds it becomes A[i-K] & A[i-K+1] & ... A[i] & ... A[i+K-1] & A[i+K]. Now this is a simple range query on a segment tree built on the array A. Likewise you must query for each element in A to get the whole array after K rounds. Also remember that the array is cyclic, so you may have to adjust your queries so that it works out.

8 Likes