CF995D Game

Allen and Bessie are playing a simple number game. They both know a function $ f: \{0, 1\}^n \to \mathbb{R} $ , i. e. the function takes $ n $ binary arguments and returns a real value. At the start of the game, the variables $ x_1, x_2, \dots, x_n $ are all set to $ -1 $ . Each round, with equal probability, one of Allen or Bessie gets to make a move. A move consists of picking an $ i $ such that $ x_i = -1 $ and either setting $ x_i \to 0 $ or $ x_i \to 1 $ . After $ n $ rounds all variables are set, and the game value resolves to $ f(x_1, x_2, \dots, x_n) $ . Allen wants to maximize the game value, and Bessie wants to minimize it. Your goal is to help Allen and Bessie find the expected game value! They will play $ r+1 $ times though, so between each game, exactly one value of $ f $ changes. In other words, between rounds $ i $ and $ i+1 $ for $ 1 \le i \le r $ , $ f(z_1, \dots, z_n) \to g_i $ for some $ (z_1, \dots, 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 $ n $ and $ r $ ( $ 1 \le n \le 18 $ , $ 0 \le r \le 2^{18} $ ). The next line contains $ 2^n $ integers $ c_0, c_1, \dots, c_{2^n-1} $ ( $ 0 \le c_i \le 10^9 $ ), denoting the initial values of $ f $ . More specifically, $ f(x_0, x_1, \dots, x_{n-1}) = c_x $ , if $ x = \overline{x_{n-1} \ldots x_0} $ in binary. Each of the next $ r $ lines contains two integers $ z $ and $ g $ ( $ 0 \le z \le 2^n - 1 $ , $ 0 \le g \le 10^9 $ ). If $ z = \overline{z_{n-1} \dots z_0} $ in binary, then this means to set $ f(z_0, \dots, z_{n-1}) \to g $ .

Print $ r+1 $ lines, the $ i $ -th of which denotes the value of the game $ f $ during the $ i $ -th round. Your answer must have absolute or relative error within $ 10^{-6} $ . Formally, let your answer be $ a $ , and the jury's answer be $ b $ . Your answer is considered correct if $ \frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6} $ .

Consider the second test case. If Allen goes first, he will set $ x_1 \to 1 $ , so the final value will be $ 3 $ . If Bessie goes first, then she will set $ x_1 \to 0 $ so the final value will be $ 2 $ . Thus the answer is $ 2.5 $ . In the third test case, the game value will always be $ 1 $ regardless of Allen and Bessie's play.