## 题意
定义一从 $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$ 次修改后的答案;每次的修改继承
预览:
定义一从 n 位 01 串映射到实数的函数 f,即 f:{0,1}n→R
现有一个 n 位的 01 串,但它其中的元素都还未确定。不妨设 xi 表示该串第 i 位的值(编号从 1 开始),未确定的值就设为 −1
又有 A,B 两位玩家,他们将共执行 n 次操作确定这个 01 串;对于每次操作,将会等概率地选择 A,B 其中一人,被选中的人则会选择 xi 满足 xi=−1,并将其设为 0 或 1
其中 A 想要最大化最终确定的串带入 f 的值,B 则想要最小化最终确定的串带入 f 的值
现给出 n,以及对每种 01 串带入 f 得到的值;问最终确定的串的期望的带入 f 得到的值
共有 r+1 组询问;但对于 r>1 组的询问,仅会修改一种 01 串带入 f 得到的值,其余和上一组询问完全相同
第一行两个整数 n,r(1≤n≤18,0≤r≤218)
第二行 2n 个整数 c0,c1,⋯,c2n−1(0≤c≤109)。这里 ci 指,若将 01 串视为一个二进制数 xn…x1,那么 ci 即为值为 i 的串带入 f 得到的值
接下来 r 行每行两个整数 z,g(0≤z≤2n−1,0≤g≤109),表示将 cz 修改为 g
共 r+1 行。第 1 行表示初始给出数据的答案,第 r+1 行表示第 r 次修改后的答案;每次的修改继承