{"problem":{"name":"「SMOI-R1」Apple","description":{"content":"LAR 有 $2^n$ 个苹果，苹果用 $0$ 到 $2^n - 1$ 编号，编号为 $i$ 的苹果的价值是 $v_i$。 如果 $A\\operatorname{or}B=A$，那么可以说 $A$ 包含 $B$（$\\operatorname{or}$ 是按位或）。 因为 LAR 的苹果太多了，所以他不知道如何挑选苹果。他想进行一些操作，方便他吃苹果。 总共有两种操作，共 $q$ 个操作： ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":680,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10408"},"statements":[{"statement_type":"Markdown","content":"LAR 有 $2^n$ 个苹果，苹果用 $0$ 到 $2^n - 1$ 编号，编号为 $i$ 的苹果的价值是 $v_i$。\n\n如果 $A\\operatorname{or}B=A$，那么可以说 $A$ 包含 $B$（$\\operatorname{or}$ 是按位或）。\n\n因为 LAR 的苹果太多了，所以他不知道如何挑选苹果。他想进行一些操作，方便他吃苹果。\n\n总共有两种操作，共 $q$ 个操作：\n\n- $1\\ S$ ，询问所有编号被 $S$ 包含的苹果的价值总和。\n- $2\\ S\\ A$ ，改变编号为 $S$ 的苹果的价值为 $A$（将 $v_S$ 改为 $A$）。\n\n## Input\n\n第一行有两个整数 $n$ 和 $q$。$q$ 代表操作次数。\n\n第二行有 $2^n$ 个数，第 $i$ 个数代表 $v_{i-1}$ 的值。\n\n接下来有 $q$ 行，每行代表 LAR 要进行的一个操作，详细见上文。\n\n## Output\n\n对于每个操作 $1$，输出一个数，代表这个询问的答案。\n\n[samples]\n\n## Background\n\n**为了卡掉错误算法，我们把时限改为 680ms。**\n\n## Note\n\n### 样例解释\n初始时 $v=[1,2,3,2]$。\n\n第一个操作时询问所有编号被 $2$ 包含的苹果的价值总和。被 $2$ 包含的数为 $0,2$，所以答案为 $v_0 + v_2=4$。\n\n第二个操作是把 $v_0$ 改为 $4$，此时 $v=[4,2,3,2]$。\n\n第三个操作时询问所有编号被 $2$ 包含的苹果的价值总和。被 $2$ 包含的数为 $0,2$，所以答案为 $v_0 + v_2=7$。\n\n第四个操作是把 $v_3$ 改为 $1$，此时 $v=[4,2,3,1]$。\n\n第五个操作时询问所有编号被 $3$ 包含的苹果的价值总和。被 $3$ 包含的数为 $0,1,2,3$，所以答案为 $v_0 + v_1 + v_2 + v_3=10$。\n### 数据范围\n**本题采用捆绑测试**。\n\nsubtask 编号|$n\\leq$|$q\\leq$|特殊性质|分值\n-|-|-|-|-\n$1$|$10$|$10^4$|无|$10$\n$2$|$16$|$3\\times 10^5$|无|$20$\n$3$|$20$|$3\\times10^5$|只有操作 1|$10$\n$4$|$20$|$10^5$|无|$20$\n$5$|$20$|$3\\times10^5$|无|$40$\n\n对于 $100\\%$ 的数据，保证 $1\\le n \\leq 20$ ，$1 \\le q\\leq3\\times10^5$，$0\\leq v_i\\leq 2^{31}-1$ 。\n\n**提示**：本题输入量较大，请使用快读。请注意代码**常数**。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10408","tags":["动态规划 DP","根号分治"],"sample_group":[["2 5\n1 2 3 2\n1 2\n2 0 4\n1 2\n2 3 1\n1 3","4\n7\n10"]],"created_at":"2026-03-03 11:09:25"}}