P10680 [COTS 2024] 双双决斗 Dvoboj

译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D1T1。$\texttt{2s,1G}$。 > Two pharaonic yellow lines turned into an eye...

Jusuf 手里有 $N$ 张卡牌，从左到右编号为 $1$ 到 $N$。每张卡牌的力量为 $p_i$。由于 Jusuf 即将参加比赛，他想要在脑中想象战斗。有时候，他也会更改卡牌的力量值。Jusuf 总共会做 $Q$ 次操作，每个操作属于以下两种类型之一： 1. `1 i r`：Jusuf 将位于位置 $i$ 的卡牌的力量设为 $r$，即 $p_i\gets r$。 2. `2 l k`：Jusuf 在脑中想象一场战斗。这场战斗使用从第 $l,l+1,\cdots,l + 2^k − 1$ 张，共 $2^k$ 张卡牌。 战斗将会进行 $k$ 轮。每轮中，Jusuf 将第 $(2i-1)$ 和第 $2i$ 张卡牌分成一组（例如第 $1$ 张和第 $2$ 张卡牌为一组）。 对于每组卡牌，Jusuf 比较它们的力量。不妨设两张卡牌的力量分别为 $A$ 和 $B$，力量更大的卡牌将获胜，且获胜卡牌的力量变为 $|A − B|$，另一张卡牌被移除。特别地，如果 $A=B$，则这场战斗的结果无法确定，将会随机一张卡牌获胜，力量变为 $0$。 注意到，在 $k$ 轮后，只会剩下一张卡牌，Jusuf 想要知道此时它的力量大小。 由于 Jusuf 只是在脑中想象战斗，所以实际上牌的数量不会改变，$p_i$ 也不会改变。

第一行，两个正整数 $N,Q$，含义见题面。 第二行，$n$ 个整数，第 $i$ 个整数表示 $p_i$。 接下来 $Q$ 行，每行 $3$ 个正整数，描述一个操作。

对于每个操作 $2$，输出一行一个整数，表示所求的力量大小。

#### 样例解释 对于样例 $1$ 的第一个询问，有： $$(\bold{\textcolor{red}{4}},8,\bold{\textcolor{red}{2}},0)\to (\bold{\textcolor{red}{4}},2)\to(2)$$ 对于样例 $1$ 的第二个询问，有： $$ (\bold{\textcolor{red}{8}},2)\to(6)$$ #### 数据范围 对于 $100\%$ 的数据，保证： - $2\le N\le 200\, 000$，$1\le Q\le 200\, 000$； - $0\le p_i\le 10^9$； - $1\le i\le N$，$0\le r\le 10^9$； - $1\le l\le N$，$1\le l+{2^k}-1\le N$。 | 子任务编号 | 分值 | 约束 | |:-----:|:------:|:-------:| | $1$ | $11$ | $N, Q \leq 1000$ | | $2$ | $13$ | $N=2^k$ | | $3$ | $16$ | $0\le p_i,r\le 1$ | | $4$ | $17$ | 不含修改操作 | | $5$ | $43$ | 无额外约束 |