{"problem":{"name":"[COTS 2024] 双双决斗 Dvoboj","description":{"content":"Jusuf 手里有 $N$ 张卡牌，从左到右编号为 $1$ 到 $N$。每张卡牌的力量为 $p_i$。由于 Jusuf 即将参加比赛，他想要在脑中想象战斗。有时候，他也会更改卡牌的力量值。Jusuf 总共会做 $Q$ 次操作，每个操作属于以下两种类型之一： 1. `1 i r`：Jusuf 将位于位置 $i$ 的卡牌的力量设为 $r$，即 $p_i\\gets r$。 2. `2 l k`：Ju","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10680"},"statements":[{"statement_type":"Markdown","content":"Jusuf 手里有 $N$ 张卡牌，从左到右编号为 $1$ 到 $N$。每张卡牌的力量为 $p_i$。由于 Jusuf 即将参加比赛，他想要在脑中想象战斗。有时候，他也会更改卡牌的力量值。Jusuf 总共会做 $Q$ 次操作，每个操作属于以下两种类型之一：\n\n1. `1 i r`：Jusuf 将位于位置 $i$ 的卡牌的力量设为 $r$，即 $p_i\\gets r$。\n\n2. `2 l k`：Jusuf 在脑中想象一场战斗。这场战斗使用从第 $l,l+1,\\cdots,l + 2^k − 1$ 张，共 $2^k$ 张卡牌。\n\n    战斗将会进行 $k$ 轮。每轮中，Jusuf 将第 $(2i-1)$ 和第 $2i$ 张卡牌分成一组（例如第 $1$ 张和第 $2$ 张卡牌为一组）。\n    \n    对于每组卡牌，Jusuf 比较它们的力量。不妨设两张卡牌的力量分别为 $A$ 和 $B$，力量更大的卡牌将获胜，且获胜卡牌的力量变为 $|A − B|$，另一张卡牌被移除。特别地，如果 $A=B$，则这场战斗的结果无法确定，将会随机一张卡牌获胜，力量变为 $0$。\n    \n    注意到，在 $k$ 轮后，只会剩下一张卡牌，Jusuf 想要知道此时它的力量大小。\n\n由于 Jusuf 只是在脑中想象战斗，所以实际上牌的数量不会改变，$p_i$ 也不会改变。\n\n## Input\n\n第一行，两个正整数 $N,Q$，含义见题面。\n\n第二行，$n$ 个整数，第 $i$ 个整数表示 $p_i$。\n\n接下来 $Q$ 行，每行 $3$ 个正整数，描述一个操作。\n\n## Output\n\n对于每个操作 $2$，输出一行一个整数，表示所求的力量大小。\n\n[samples]\n\n## Background\n\n译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D1T1。$\\texttt{2s,1G}$。\n\n> Two pharaonic yellow lines turned into an eye...\n\n## Note\n\n#### 样例解释\n\n对于样例 $1$ 的第一个询问，有：\n\n$$(\\bold{\\textcolor{red}{4}},8,\\bold{\\textcolor{red}{2}},0)\\to (\\bold{\\textcolor{red}{4}},2)\\to(2)$$\n\n对于样例 $1$ 的第二个询问，有：\n\n$$ (\\bold{\\textcolor{red}{8}},2)\\to(6)$$\n\n#### 数据范围\n\n对于 $100\\%$ 的数据，保证：\n\n- $2\\le N\\le 200\\, 000$，$1\\le Q\\le 200\\, 000$；\n- $0\\le p_i\\le 10^9$；\n- $1\\le i\\le N$，$0\\le r\\le 10^9$；\n- $1\\le l\\le N$，$1\\le l+{2^k}-1\\le N$。\n\n| 子任务编号 | 分值 | 约束  |\n|:-----:|:------:|:-------:|\n| $1$   | $11$    | $N, Q \\leq 1000$ |\n| $2$    | $13$    | $N=2^k$ |\n| $3$    | $16$    | $0\\le p_i,r\\le 1$ |\n| $4$    | $17$    | 不含修改操作 |\n| $5$    | $43$    | 无额外约束 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10680","tags":["2024","O2优化","ST 表","根号分治","COTS（克罗地亚）"],"sample_group":[["5 3\n4 8 2 0 7\n2 1 2\n1 1 9\n2 2 1","2\n6"],["8 6\n1 2 3 4 5 6 7 8\n2 1 3\n1 4 1\n1 7 3\n2 1 3\n1 2 100\n2 2 2","0\n3\n93"],["9 5\n1 0 2 0 4 1 3 2 8\n2 2 3\n2 1 3\n1 5 1\n1 6 4\n2 4 2","2\n1\n0"]],"created_at":"2026-03-03 11:09:25"}}