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 将序列恢复到初始状态。

第一行也是唯一一行包含 5 个整数 $n,m,A,p,q$。($1 \leq n \leq 10^6$, $1 \leq m \leq 10^6$, $1 \leq A \leq 19\,260\,817$, $1 \leq p \leq 4$, $1 \leq q \leq 30$) 请注意！为了避免输入文件过大，真实输入是通过以下策略构造的： $\textbf{func rnd():}\ \ \ \\ A \leftarrow (7A+13) \bmod 19\,260\,817\ \ \ \\ \textbf{return } A$ 首先，生成 $n$ 个整数 $a_1,a_2,\cdots,a_n$，依次生成，$a_i \leftarrow rnd() \bmod q + 1$。 然后，生成所有操作的参数。 对于每个操作，首先生成操作编号（用 $opt$ 表示），$opt \leftarrow rnd() \bmod p + 1$。 根据操作编号，不同的操作使用不同的方法生成参数。 - 对于操作 1：需要通过以下方式获取 $l$ 和 $r$： - $L \leftarrow rnd() \bmod n + 1$ - $R \leftarrow rnd() \bmod n + 1$ - $l \leftarrow \min(L,R)$ - $r \leftarrow \max(L,R)$ - 对于操作 2：需要通过以下方式获取 $l,r$ 和 $k$： - $L \leftarrow rnd() \bmod n + 1$ - $R \leftarrow rnd() \bmod n + 1$ - $l \leftarrow \min(L,R)$ - $r \leftarrow \max(L,R)$ - $k \leftarrow rnd() \bmod q + 1$ - 对于操作 3：需要通过以下方式获取 $pos$ 和 $k$： - $pos \leftarrow rnd() \bmod n + 1$ - $k \leftarrow rnd() \bmod q + 1$ - 对于操作 4：需要通过以下方式获取 $t$： - $t \leftarrow rnd() \bmod i$ 这里，$i$ 表示第 $i$ 次操作。

对于每个操作 1 和 2，你需要输出一行整数，表示操作 1 和 2 的答案对 $10^9 + 7$ 取模的结果。

函数 `max` 表示参数中的最大值。函数 `min` 表示参数中的最小值。 在例子 1 中，初始书为 $[1,2,3,1,2,3]$。三个操作的范围分别是 $[4,4]$，$[1,3]$ 和 $[4,5]$。（由 ChatGPT 4o 翻译）