{"problem":{"name":"F. Game","description":{"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 g","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF996F"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe 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$.\n\n## Output\n\nPrint $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}$.\n\n[samples]\n\n## Note\n\nConsider 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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 \\le i \\le r$），$f (z_1, \\dots, z_n)$ 会被更新为 $g_i$，其中 $(z_1, \\dots, z_n) \\in \\{0, 1\\}^n$。你需要求出初始时刻以及每次变化后的期望游戏值。\n\n第一行包含两个整数 $n$ 和 $r$（$1 \\le n \\le 18$，$0 \\le r \\le 2^{18}$）。\n\n接下来一行包含 $2^n$ 个整数 $c_0, c_1, \\dots, c_{2^n -1}$（$0 \\le c_i \\le 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 \\le z \\le 2^n -1$，$0 \\le g \\le 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 |)} \\le 10^{-6}$ 时，你的答案被视为正确。\n\n考虑第二个测试用例：若 Allen 先行动，他会将 $x_1$ 设为 $1$，因此最终值为 $3$；若 Bessie 先行动，她会将 $x_1$ 设为 $0$，因此最终值为 $2$。因此答案为 $2.5$。\n\n在第三个测试用例中，无论 Allen 和 Bessie 如何行动，游戏值始终为 $1$。\n\n## Input\n\n第一行包含两个整数 $n$ 和 $r$（$1 \\le n \\le 18$，$0 \\le r \\le 2^{18}$）。接下来一行包含 $2^n$ 个整数 $c_0, c_1, \\dots, c_{2^n -1}$（$0 \\le c_i \\le 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 \\le z \\le 2^n -1$，$0 \\le g \\le 10^9$）。若 $z = \\overline{z_{n-1} \\dots z_0}$（二进制表示），则表示将 $f (z_0, \\dots, z_{n-1})$ 设为 $g$。\n\n## Output\n\n请输出 $r + 1$ 行，第 $i$ 行表示第 $i$ 轮游戏的 $f$ 值。你的答案绝对误差或相对误差不得超过 $10^{-6}$。形式化地，设你的答案为 $a$，标准答案为 $b$，当且仅当 $\\frac{| a - b |}{\\max (1, | b |)} \\le 10^{-6}$ 时，你的答案被视为正确。\n\n[samples]\n\n## Note\n\n考虑第二个测试用例：若 Allen 先行动，他会将 $x_1$ 设为 $1$，因此最终值为 $3$；若 Bessie 先行动，她会将 $x_1$ 设为 $0$，因此最终值为 $2$。因此答案为 $2.5$。在第三个测试用例中，无论 Allen 和 Bessie 如何行动，游戏值始终为 $1$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**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 $ (little-endian binary representation).  \n\nLet $ \\mathbf{x} = (x_1, x_2, \\dots, x_n) \\in \\{-1, 0, 1\\}^n $ denote the state vector, initially $ \\mathbf{x} = (-1, -1, \\dots, -1) $.  \nEach round, a player (Allen or Bessie, chosen uniformly at random) selects an index $ i $ with $ x_i = -1 $ and sets $ x_i \\in \\{0,1\\} $.  \nAllen aims to **maximize** $ f(\\mathbf{x}) $; Bessie aims to **minimize** it.  \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, 1, \\dots, 2^n - 1\\} $  \n4. Each update: $ z \\in \\{0, 1, \\dots, 2^n - 1\\} $, $ g \\in [0, 10^9] $, set $ c_z \\leftarrow g $  \n\n**Objective**  \nCompute $ V(\\mathbf{-1}) $, the expected value of the game starting from $ \\mathbf{x} = (-1, \\dots, -1) $, after each of $ r+1 $ updates to $ f $ (including the initial state).  \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 $ S = \\{ i \\mid x_i = -1 \\} $, $ m = |S| $.  \n  Then:  \n  $$\n  V(\\mathbf{x}) = \\frac{1}{2m} \\sum_{i \\in S} \\left( \\max_{b \\in \\{0,1\\}} V(\\mathbf{x}[i \\leftarrow b]) + \\min_{b \\in \\{0,1\\}} V(\\mathbf{x}[i \\leftarrow b]) \\right)\n  $$  \n  (Because with probability $ \\frac{1}{2} $, Allen moves and chooses $ \\arg\\max $, and with probability $ \\frac{1}{2} $, Bessie moves and chooses $ \\arg\\min $, and each $ i \\in S $ is chosen uniformly.)  \n\nEquivalently, for each unset variable $ i $, the contribution is the average of the max and min over its two possible assignments:  \n$$\nV(\\mathbf{x}) = \\frac{1}{|S|} \\sum_{i \\in S} \\frac{ V(\\mathbf{x}[i \\leftarrow 0]) + V(\\mathbf{x}[i \\leftarrow 1]) }{2}\n$$\n\nThus, the value at any state depends only on the values of its immediate extensions, and the full function $ f $ is updated dynamically.  \n\nWe are to output $ V(\\mathbf{-1}) $ after each update to $ f $, for $ r+1 $ total outputs.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF996F","tags":["math"],"sample_group":[["2 2\n0 1 2 3\n2 5\n0 4","1.500000\n2.250000\n3.250000"],["1 0\n2 3","2.500000"],["2 0\n1 1 1 1","1.000000"]],"created_at":"2026-03-03 11:00:39"}}