Multidimensional Expectations#11527
Alice and Bob are playing a simple number game. They both know a function f:\{0,1\}^n \to \mathbb R, i. e. the function takes binary arguments and returns a real value. At the start of the game, the variables x_1,x_2,...,x_n are all set to . Each round, with equal probability, one of Alice or Bob gets to make a move. A move consists of picking an such that x_i=−1 and either setting x_i \to 0 or x_i \to 1.
After rounds all variables are set, and the game value resolves to f(x_1,x_2,...,x_n). Alice wants to maximize the game value, and Bob wants to minimize it.
Your goal is to help Alice and Bob find the expected game value! They will play r+1 times though, so between each game, exactly one value of changes. In other words, between rounds and i+1 for 1 \le i \le r, f(z_1, ..., z_n) \to g_i for some (z_1, ..., z_n) \in \{0,1\}^n. You are to find the expected game value in the beginning and after each change.
The first line contains two integers and (1 \le n \le 18, 0 \le r \le 2^{18}).
The next line contains 2^n integers c_0,c_1, ..., c_{2^n−1} (0 \le c_i \le 10^9), denoting the initial values of . More specifically, f(x_0,x_1,...,x_{n−1})=c_x, if x=\overline{x_{n−1}...x_0} in binary.
Each of the next lines contains two integers and (0 \le z \le 2^n−1, 0 \le g \le 10^9). If z=\overline{z_{n−1}...z_0} in binary, then this means to set f(z_0,...,z_{n−1}) \to g.
Print r+1 lines, the -th of which denotes the value of the game during the -th round. Your answer must have absolute or relative error within 10^{−6}.
Formally, let your answer be , and the jury's answer be . Your answer is considered correct if \frac{|a−b|}{max(1,|b|)} \le 10^{−6}.
Example 1
Example 2
Example 3
Consider the second test case. If Alice goes first, she will set x_1 \to 1, so the final value will be . If Bob goes first, then he will set x_1 \to 0 so the final value will be . Thus the answer is .
In the third test case, the game value will always be regardless of Alice and Bob's play.