E2. Bitwise Queries (Hard Version)
bitmasks; constructive algorithms; interactive; math
The only difference between the easy and hard versions is the constraints on the number of queries.This is an interactive problem.Ridbit has a hidden array \(a\) of \(n\) integers which he wants Ashish to guess. Note that \(n\) is a power of two. Ashish is allowed to ask three different types of queries. They are of the form AND \(i\) \(j\): ask for the bitwise AND of elements \(a_i\) and \(a_j\) \((1 \leq i, j \le n\), \(i \neq j)\) OR \(i\) \(j\): ask for the bitwise OR of elements \(a_i\) and \(a_j\) \((1 \leq i, j \le n\), \(i \neq j)\) XOR \(i\) \(j\): ask for the bitwise XOR of elements \(a_i\) and \(a_j\) \((1 \leq i, j \le n\), \(i \neq j)\) Can you help Ashish guess the elements of the array?In this version, each element takes a value in the range \([0, n-1]\) (inclusive) and Ashish can ask no more than \(n+1\) queries.
The first line of input contains one integer \(n\) \((4 \le n \le 2^{16})\) — the length of the array. It is guaranteed that \(n\) is a power of two.
The array \(a\) in the example is \([0, 0, 2, 3]\).