{"raw_statement":[{"iden":"statement","content":"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$.\n\nAfter $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.\n\nYour 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."},{"iden":"input","content":"The first line contains two integers $n$ and $r$ ($1 \\le n \\le 18$, $0 \\le r \\le 2^{18}$).\n\nThe 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.\n\nEach 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$."},{"iden":"output","content":"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}$.\n\nFormally, 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}$."},{"iden":"examples","content":"Input\n\n2 2\n0 1 2 3\n2 5\n0 4\n\nOutput\n\n1.500000\n2.250000\n3.250000\n\nInput\n\n1 0\n2 3\n\nOutput\n\n2.500000\n\nInput\n\n2 0\n1 1 1 1\n\nOutput\n\n1.000000"},{"iden":"note","content":"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$.\n\nIn the third test case, the game value will always be $1$ regardless of Allen and Bessie's play."}],"translated_statement":[{"iden":"statement","content":"Allen 和 Bessie 正在玩一个简单的数字游戏。他们都知道一个函数 $f : {0, 1}^n \\to \\mathbb{R}$，即该函数接受 $n$ 个二进制参数并返回一个实数值。游戏开始时，变量 $x_1, x_2, \\dots, x_n$ 均被设为 $-1$。每一轮，Allen 或 Bessie 以相等概率获得一次移动机会。一次移动是指选择一个满足 $x_i = -1$ 的 $i$，并将 $x_i$ 设为 $0$ 或 $1$。\n\n经过 $n$ 轮后，所有变量均被设定，游戏值确定为 $f(x_1, x_2, \\dots, x_n)$。Allen 希望最大化游戏值，而 Bessie 希望最小化它。\n\n你的目标是帮助 Allen 和 Bessie 计算游戏的期望值！不过他们会进行 $r + 1$ 次游戏，因此在每两次游戏之间，恰好有一个 $f$ 的值会发生变化。换句话说，在第 $i$ 轮和第 $i + 1$ 轮之间（$1 \\leq i \\leq r$），$f(z_1, \\dots, z_n)$ 会被设为 $g_i$，其中 $(z_1, \\dots, z_n) \\in \\{0, 1\\}^n$。你需要求出初始时刻以及每次变化后的期望游戏值。\n\n第一行包含两个整数 $n$ 和 $r$（$1 \\leq n \\leq 18$，$0 \\leq r \\leq 2^{18}$）。\n\n下一行包含 $2^n$ 个整数 $c_0, c_1, \\dots, c_{2^n - 1}$（$0 \\leq c_i \\leq 10^9$），表示 $f$ 的初始值。更具体地，若 $x = \\overline{x_{n-1} \\dots x_0}$（二进制表示），则 $f(x_0, x_1, \\dots, x_{n-1}) = c_x$。\n\n接下来的 $r$ 行，每行包含两个整数 $z$ 和 $g$（$0 \\leq z \\leq 2^n - 1$，$0 \\leq g \\leq 10^9$）。若 $z = \\overline{z_{n-1} \\dots z_0}$（二进制表示），则表示将 $f(z_0, \\dots, z_{n-1})$ 设为 $g$。\n\n请输出 $r + 1$ 行，第 $i$ 行表示第 $i$ 轮游戏的 $f$ 值。你的答案必须满足绝对误差或相对误差不超过 $10^{-6}$。\n\n形式化地，设你的答案为 $a$，标准答案为 $b$，若 $\\frac{|a - b|}{\\max(1, |b|)} \\leq 10^{-6}$，则你的答案被视为正确。\n\n考虑第二个测试用例。若 Allen 先手，他会将 $x_1 \\to 1$，因此最终值为 $3$。若 Bessie 先手，她会将 $x_1 \\to 0$，因此最终值为 $2$。因此答案为 $2.5$。\n\n在第三个测试用例中，无论 Allen 和 Bessie 如何操作，游戏值始终为 $1$。"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $r$（$1 \\leq n \\leq 18$，$0 \\leq r \\leq 2^{18}$）。下一行包含 $2^n$ 个整数 $c_0, c_1, \\dots, c_{2^n - 1}$（$0 \\leq c_i \\leq 10^9$），表示 $f$ 的初始值。更具体地，若 $x = \\overline{x_{n-1} \\dots x_0}$（二进制表示），则 $f(x_0, x_1, \\dots, x_{n-1}) = c_x$。接下来的 $r$ 行，每行包含两个整数 $z$ 和 $g$（$0 \\leq z \\leq 2^n - 1$，$0 \\leq g \\leq 10^9$）。若 $z = \\overline{z_{n-1} \\dots z_0}$（二进制表示），则表示将 $f(z_0, \\dots, z_{n-1})$ 设为 $g$。"},{"iden":"output","content":"请输出 $r + 1$ 行，第 $i$ 行表示第 $i$ 轮游戏的 $f$ 值。你的答案必须满足绝对误差或相对误差不超过 $10^{-6}$。形式化地，设你的答案为 $a$，标准答案为 $b$，若 $\\frac{|a - b|}{\\max(1, |b|)} \\leq 10^{-6}$，则你的答案被视为正确。"},{"iden":"examples","content":"输入\n2 2\n0 1 2 3\n2 5\n0 4\n输出\n1.500000\n2.250000\n3.250000\n\n输入\n1 0\n2 3\n输出\n2.500000\n\n输入\n2 0\n1 1 1 1\n输出\n1.000000"},{"iden":"note","content":"考虑第二个测试用例。若 Allen 先手，他会将 $x_1 \\to 1$，因此最终值为 $3$。若 Bessie 先手，她会将 $x_1 \\to 0$，因此最终值为 $2$。因此答案为 $2.5$。在第三个测试用例中，无论 Allen 和 Bessie 如何操作，游戏值始终为 $1$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ r \\in \\mathbb{Z}_{\\geq 0} $.  \nLet $ f: \\{0,1\\}^n \\to \\mathbb{R} $ be a function represented by a vector $ \\mathbf{c} = (c_0, c_1, \\dots, c_{2^n - 1}) $, where $ c_x = f(x_0, x_1, \\dots, x_{n-1}) $ for $ x = \\sum_{i=0}^{n-1} x_i 2^i $.  \n\nLet $ \\mathbf{x} = (x_1, \\dots, x_n) \\in \\{-1, 0, 1\\}^n $ denote the state vector, initially $ \\mathbf{x} = (-1, \\dots, -1) $.  \nIn each round, an unset variable $ x_i = -1 $ is chosen uniformly at random, and then set to 0 or 1 by the current player:  \n- Allen (maximizer) and Bessie (minimizer) alternate turns, with each player chosen uniformly at random with probability $ \\frac{1}{2} $ per turn, independently.  \n\nLet $ V(\\mathbf{x}) $ denote the expected game value from state $ \\mathbf{x} $ under optimal play.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 18 $  \n2. $ 0 \\leq r \\leq 2^{18} $  \n3. $ 0 \\leq c_i \\leq 10^9 $ for all $ i \\in \\{0, \\dots, 2^n - 1\\} $  \n4. Each update: $ z \\in \\{0, \\dots, 2^n - 1\\} $, $ g \\in [0, 10^9] $, set $ c_z \\leftarrow g $  \n\n**Objective**  \nCompute $ V(\\mathbf{-1}) $, the expected game value starting from all variables unset, for the initial $ \\mathbf{c} $, and after each of the $ r $ updates.  \n\nThe recurrence for $ V(\\mathbf{x}) $ is:  \n- If $ \\mathbf{x} \\in \\{0,1\\}^n $, then $ V(\\mathbf{x}) = f(\\mathbf{x}) $.  \n- Otherwise, let $ k = |\\{i : x_i = -1\\}| > 0 $.  \n  Then:  \n  $$\n  V(\\mathbf{x}) = \\frac{1}{2} \\left( \\frac{1}{k} \\sum_{\\substack{i: x_i = -1}} \\max_{b \\in \\{0,1\\}} V(\\mathbf{x}[i \\leftarrow b]) \\right) + \\frac{1}{2} \\left( \\frac{1}{k} \\sum_{\\substack{i: x_i = -1}} \\min_{b \\in \\{0,1\\}} V(\\mathbf{x}[i \\leftarrow b]) \\right)\n  $$\n\nOutput $ V(\\mathbf{-1}) $ after the initial configuration and after each of the $ r $ updates.","simple_statement":null,"has_page_source":false}