HUSTOJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
Login
Register
1706: P10680 [COTS 2024] 双双决斗 Dvoboj
内存限制：1024 MB
时间限制：2.000 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：0
通过：0
提交
提交记录
统计
Web Board
题目描述
## 题目背景
译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D1T1。
2s,1G
\texttt{2s,1G}
2s,1G
。
> Two pharaonic yellow lines turned into an eye...
## 题目描述
Jusuf 手里有
N
N
N
张卡牌，从左到右编号为
1
1
1
到
N
N
N
。每张卡牌的力量为
p
i
p_i
p
i
。由于 Jusuf 即将参加比赛，他想要在脑中想象战斗。有时候，他也会更改卡牌的力量值。Jusuf 总共会做
Q
Q
Q
次操作，每个操作属于以下两种类型之一：
1. `1 i r`：Jusuf 将位于位置
i
i
i
的卡牌的力量设为
r
r
r
，即
p
i
←
r
p_i\gets r
p
i
←
r
。
2. `2 l k`：Jusuf 在脑中想象一场战斗。这场战斗使用从第
l
,
l
+
1
,
⋯
,
l
+
2
k
−
1
l,l+1,\cdots,l + 2^k − 1
l
,
l
+
1
,
⋯
,
l
+
2
k
−
1
张，共
2
k
2^k
2
k
张卡牌。
战斗将会进行
k
k
k
轮。每轮中，Jusuf 将第
(
2
i
−
1
)
(2i-1)
(
2
i
−
1
)
和第
2
i
2i
2
i
张卡牌分成一组（例如第
1
1
1
张和第
2
2
2
张卡牌为一组）。
对于每组卡牌，Jusuf 比较它们的力量。不妨设两张卡牌的力量分别为
A
A
A
和
B
B
B
，力量更大的卡牌将获胜，且获胜卡牌的力量变为
∣
A
−
B
∣
|A − B|
∣
A
−
B
∣
，另一张卡牌被移除。特别地，如果
A
=
B
A=B
A
=
B
，则这场战斗的结果无法确定，将会随机一张卡牌获胜，力量变为
0
0
0
。
注意到，在
k
k
k
轮后，只会剩下一张卡牌，Jusuf 想要知道此时它的力量大小。
由于 Jusuf 只是在脑中想象战斗，所以实际上牌的数量不会改变，
p
i
p_i
p
i
也不会改变。
输入格式
第一行，两个正整数
N
,
Q
N,Q
N
,
Q
，含义见题面。
第二行，
n
n
n
个整数，第
i
i
i
个整数表示
p
i
p_i
p
i
。
接下来
Q
Q
Q
行，每行
3
3
3
个正整数，描述一个操作。
输出格式
对于每个操作
2
2
2
，输出一行一个整数，表示所求的力量大小。
输入样例
复制
5 3 4 8 2 0 7 2 1 2 1 1 9 2 2 1
输出样例
复制
2 6
数据范围与提示
#### 样例解释
对于样例 的第一个询问，有：
(
4
,
8
,
2
,
0
)
→
(
4
,
2
)
→
(
2
)
(\bold{\textcolor{red}{4}},8,\bold{\textcolor{red}{2}},0)\to (\bold{\textcolor{red}{4}},2)\to(2)
(
4
,
8
,
2
,
0
)
→
(
4
,
2
)
→
(
2
)
对于样例的第二个询问，有：
(
8
,
2
)
→
(
6
)
(\bold{\textcolor{red}{8}},2)\to(6)
(
8
,
2
)
→
(
6
)
#### 数据范围
对于
100
%
100\%
1
0
0
%
的数据，保证：
-
2
≤
N
≤
200
000
2\le N\le 200\, 000
2
≤
N
≤
2
0
0
0
0
0
，
1
≤
Q
≤
200
000
1\le Q\le 200\, 000
1
≤
Q
≤
2
0
0
0
0
0
；
-
0
≤
p
i
≤
1
0
9
0\le p_i\le 10^9
0
≤
p
i
≤
1
0
9
；
-
1
≤
i
≤
N
1\le i\le N
1
≤
i
≤
N
，
0
≤
r
≤
1
0
9
0\le r\le 10^9
0
≤
r
≤
1
0
9
；
-
1
≤
l
≤
N
1\le l\le N
1
≤
l
≤
N
，
1
≤
l
+
2
k
−
1
≤
N
1\le l+{2^k}-1\le N
1
≤
l
+
2
k
−
1
≤
N
。
| 子任务编号 | 分值 | 约束 |
|:-----:|:------:|:-------:|
|
1
1
1
|
11
11
1
1
|
N
,
Q
≤
1000
N, Q \leq 1000
N
,
Q
≤
1
0
0
0
|
|
2
2
2
|
13
13
1
3
|
N
=
2
k
N=2^k
N
=
2
k
|
|
3
3
3
|
16
16
1
6
|
0
≤
p
i
,
r
≤
1
0\le p_i,r\le 1
0
≤
p
i
,
r
≤
1
|
|
4
4
4
|
17
17
1
7
| 不含修改操作 |
|
5
5
5
|
43
43
4
3
| 无额外约束 |
分类标签
ST表
根号分治