题目背景

译自 Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection) 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$，输出一行一个整数，表示所求的力量大小。

5 3
4 8 2 0 7
2 1 2
1 1 9
2 2 1

2
6

8 6
1 2 3 4 5 6 7 8
2 1 3
1 4 1
1 7 3
2 1 3
1 2 100
2 2 2

0
3
93

9 5
1 0 2 0 4 1 3 2 8
2 2 3
2 1 3
1 5 1
1 6 4
2 4 2

2
1
0

提示

样例解释

对于样例 $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$	无额外约束