Game

## 题意 定义一从 $n$ 位 $\texttt{01}$ 串映射到实数的函数 $f$，即 $f:\{0, 1\}^n \to \mathbb{R}$ 现有一个 $n$ 位的 $\texttt{01}$ 串，但它其中的元素都还未确定。不妨设 $x_i$ 表示该串第 $i$ 位的值（编号从 $1$ 开始），未确定的值就设为 $-1$ 又有 $\texttt{A}, \texttt{B}$ 两位玩家，他们将共执行 $n$ 次操作确定这个 $\texttt{01}$ 串；对于每次操作，将会等概率地选择 $\texttt{A}, \texttt{B}$ 其中一人，被选中的人则会选择 $x_i$ 满足 $x_i=-1$，并将其设为 $0$ 或 $1$ 其中 $\texttt{A}$ 想要最大化最终确定的串带入 $f$ 的值，$\texttt{B}$ 则想要最小化最终确定的串带入 $f$ 的值 现给出 $n$，以及对每种 $\texttt{01}$ 串带入 $f$ 得到的值；问最终确定的串的期望的带入 $f$ 得到的值 共有 $r+1$ 组询问；但对于 $r>1$ 组的询问，仅会修改一种 $\texttt{01}$ 串带入 $f$ 得到的值，其余和上一组询问完全相同 ## 输入格式 第一行两个整数 $n, r$（$1\leq n\leq 18, 0\leq r\leq 2^{18}$） 第二行 $2^n$ 个整数 $c_0, c_1, \cdots, c_{2^{n-1}}$（$0\leq c\leq 10^9$）。这里 $c_i$ 指，若将 $\texttt{01}$ 串视为一个二进制数 $\overline{x_n \ldots x_1} $，那么 $c_i$ 即为值为 $i$ 的串带入 $f$ 得到的值 接下来 $r$ 行每行两个整数 $z, g$（$0\leq z\leq 2^n-1, 0\leq g\leq 10^9$），表示将 $c_z$ 修改为 $g$ ## 输出格式 共 $r+1$ 行。第 $1$ 行表示初始给出数据的答案，第 $r+1$ 行表示第 $r$ 次修改后的答案；每次的修改继承

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} $ .

2 2
0 1 2 3
2 5
0 4

1.500000
2.250000
3.250000

1 0
2 3

2.500000

2 0
1 1 1 1

1.000000

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.