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