P10863 [HBCPC2024] Enchanted
题目描述
在《Minecraft》中，变得更强的一种方式是让盔甲和武器附魔。附魔书在其中扮演了重要角色。
附魔书最重要的属性是其等级。等级越高，书越好。我们可以将两本相同等级 $l$ 的书合并成一本新书（原来的两本书将消失）。新书的等级为 $l+1$，合并的费用为 $2^{l+1}$。
现在，Steve 有 $n$ 本编号从 $1$ 到 $n$ 的附魔书。最初，第 $i$ 本书的等级为 $a_i$。Steve 请你帮助他完成以下四种操作。
1. 给定两个整数 $l,r(1 \le l \le r \le n)$，计算通过合并编号从 $l$ 到 $r$ 的书能达到的最大等级。
2. 给定三个整数 $l,r(1 \le l \le r \le n)$ 和 $k$，然后按照以下步骤操作：
步骤 $1$：Steve 合并编号从 $l$ 到 $r$ 的所有书，直到不存在两本等级相同的书。
步骤 $2$：Steve 将一个新书等级为 $k$ 的书加入步骤 $1$ 中得到的书中。
步骤 $3$：Steve 需要合并步骤 $2$ 中得到的书，并希望最大化合并次数。
请计算并输出步骤 $3$ 中的总费用对 $10^9+7$ 取模的结果。
\textbf{注意，计算后，序列会恢复。也就是说，此操作实际上不会改变序列。}
3. 给定两个整数 $pos,k$，Steve 将编号为 $pos$ 的书的等级改为 $k$。
4. 给定一个整数 $t$，Steve 将序列恢复到第 $t$ 次操作后的状态。如果 $t=0$，则 Steve 将序列恢复到初始状态。
输入格式
无
输出格式
无
说明/提示
函数 `max` 表示参数中的最大值。函数 `min` 表示参数中的最小值。
在例子 1 中，初始书为 $[1,2,3,1,2,3]$。三个操作的范围分别是 $[4,4]$，$[1,3]$ 和 $[4,5]$。（由 ChatGPT 4o 翻译）