P15495 [ICPC 2025 APC] Tower of Hanoi

去年在河内参加 ICPC 亚太锦标赛时，你了解到了著名的汉诺塔问题。在该问题中，有三个柱子和若干个半径互不相同的圆盘，这些圆盘可以套在任何柱子上。柱子编号为 $1$ 到 $3$。在任何时刻，每个圆盘必须位于某个柱子上，且每个柱子上的圆盘必须按照半径从上到下递增的顺序堆叠。一步操作中，你可以将一个柱子顶部的圆盘移动到另一个柱子的顶部，前提是此移动不违反上述限制。目标是用最少的步数将所有圆盘移动到 $1$ 号柱子上。 你现在要解决这个著名问题的一个扩展版本。你有一个长度为 $n$ 的整数序列 $p_1, p_2, \ldots, p_n$，其初始值已给定。 此外，你还会收到 $q$ 个操作。每个操作是以下两种之一： - **修改操作：** 给定两个整数 $x$ 和 $y$。此操作要求你将 $p_x$ 的值修改为 $y$。 - **求解操作：** 给定两个整数 $l$ 和 $r$。此操作要求你求解一个有 $r - l + 1$ 个圆盘的汉诺塔问题，这些圆盘的半径分别为 $l, l+1, \ldots, r$，其中半径为 $i$ 的圆盘初始时位于柱子 $p_i$ 上（对于每个 $l\le i\le r$）。每个柱子上初始圆盘的堆叠顺序满足前述限制。你需要求出将所有圆盘移动到 $1$ 号柱子的最少步数，并对 $998\,244\,353$ 取模。 你的任务是按顺序执行所有给定的操作。

输入的第一行包含两个整数 $n$ 和 $q$（$1\le n\le 100\,000$；$1\le q\le 100\,000$）。第二行包含 $n$ 个整数，表示 $p_1, p_2, \ldots, p_n$ 的初始值（$1\le p_i\le 3$）。接下来的 $q$ 行按执行顺序表示操作。每行是以下两种格式之一： 1. `c x y`（$1\le x\le n$；$1\le y\le 3$）：对指定的整数 $x$ 和 $y$ 执行修改操作。 2. `s l r`（$1\le l\le r\le n$）：对指定的整数 $l$ 和 $r$ 执行求解操作。 输入中至少包含一个求解操作。

对于每个求解操作，按顺序输出将半径为 $l, l+1, \ldots, r$ 的圆盘全部移动到 $1$ 号柱子的最少步数，对 $998\,244\,353$ 取模后的结果。

**样例输入/输出 #1 的解释** 第一个操作要求你求解一个汉诺塔问题，其中半径分别为 $2$、$3$ 和 $4$ 的圆盘初始时分别位于 $3$ 号、$1$ 号和 $3$ 号柱子上。所有圆盘可以在 $6$ 步内移动到 $1$ 号柱子，如图 D.1 所示。 :::align{center}  图 D.1：将所有圆盘移动到 1 号柱子的 6 个步骤。阴影柱子表示最后一步移动到的柱子。 ::: 第二个操作要求你求解一个汉诺塔问题，其中半径分别为 $1$、$2$ 和 $3$ 的圆盘初始时分别位于 $2$ 号、$3$ 号和 $1$ 号柱子上。 第四个操作要求你求解一个汉诺塔问题，其中半径分别为 $2$、$3$ 和 $4$ 的圆盘初始时均位于 $3$ 号柱子上。 翻译由 DeepSeek 完成