GCOM - GOOD COMMUNICATION
Image Link : In case image is not visible ( Link )
Binary Representation of a number represents a point (vertex) in the N-th dimensional hyper-cube (N is the number of bits used to represent the number in binary form ) . Eg. point 3(011) and 5(101) are shown in 3-dimensional cube in the figure. As the value of points increases, number of axes to represent it in the hyper-cube increases .
Given an N-th dimensional hyper-cube and an array (of size n ) of selected points from the cube . We select its complementary point from the cube . We call communication between these points " GOOD " if the distance between given point and its complementary point is maximum . Distance between two points is defined as the bitwise XOR of two points . Let this complementary point be M . The cost of building communication between them is given by
Cost = 2 (n) ; where n is position of unset bit which is at farthest distance from MSB in M
To decrease the cost we have two operations :
Type1: ' q l r ' :- we select two positions l and r from the array. Output the point from the array, between the smaller and larger position being selected , which has minimum cost of building the communication .In case there are multiple answers , print the point with minimun value
Type2: ' u x y ' :- update the point at index x with value y
NOTE:- ' l r x ' are according to 1-based indexing (1 <= l,r <= n)
1 <= T <= 20
1 <= n , q <= 105
1 <= array elements <= 109
Input: First Line contains number of test cases. Next Line contains n and q representing size of array and number of operations . Next line contains array elements . Next q lines operations of type1 and type2 in the specified format
Output: Give answer of the required type in new lines .
2 3 4
q 1 3
u 2 5
q 1 2
Optimized cin/cout gets time limit, scanf/printf gets acccepted.
AC in one go!!
I have added the image link you can view it from there .
Could you check my last submission?
Please use https://www.spoj.com/uploads/ for images so that their visibility does not depend on 3rd party servers.