CF995D 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$ 次修改后的答案；每次的修改继承

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.