以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Problem D
Tower of Hanoi
Time limit: 2 seconds
While visiting Hanoi to compete in The ICPC Asia Pacific Championship last year, you learned about the famous
Tower of Hanoi problem. In the problem, there are three rods and several disks of distinct radii, which can slide onto
any rod. The rods are numbered from 1 to 3. At any point in time, each disk must be stacked on one of the rods, and
the disks stacked on each rod must be arranged in increasing order of radius from top to bottom. In one step, you can
move the disk on top of one rod to the top of another rod, provided this move does not violate the restriction above.
The goal is to move all the disks to rod 1 in the minimum number of steps.
You are solving an extension of this famous problem. You have a sequence of n integers p1, p2, . . . , pn, the initial
values of which are given to you.
You are also given q operations. Each operation is either of the following:
Change operation: Two integers x and y are given. This operation requires you to change the value of px to y.
Solve operation: Two integers l and r are given. This operation requires you to solve the Tower of Hanoi problem
with r −l + 1 disks of radii l, l + 1, . . . , r, where the disk of radius i is initially stacked on rod pi, for each
l ≤i ≤r. The order of the disks initially stacked on each rod satisfies the restriction explained earlier. You
need to find the minimum number of steps to move all disks to rod 1 modulo 998 244 353.
Your task is to perform all the given operations sequentially.
Input
The first line of input contains two integers n and q (1 ≤n ≤100 000; 1 ≤q ≤100 000). The second line contains n
integers representing the initial values of p1, p2, . . . , pn (1 ≤pi ≤3). The next q lines represent the operations in the
order they are to be performed. Each line is in one of the following formats:
1. “c x y” (1 ≤x ≤n; 1 ≤y ≤3) to apply a Change operation for the specified integers x and y.
2. “s l r” (1 ≤l ≤r ≤n) to apply a Solve operation for the specified integers l and r.
The input contains at least one Solve operation.
Output
For each Solve operation, in order, output the minimum number of steps to solve the Tower of Hanoi problem with
disks of radii l, l + 1, . . . , r modulo 998 244 353.
Sample Input #1 Sample Output #1
4 4 6
2 3 1 3 2
s 2 4 7
s 1 3
c 3 3
s 2 4
The 2025 ICPC Asia Pacific Championship Problem D: Tower of Hanoi
Explanation for the sample input/output #1
The first operation requires you to solve the Tower of Hanoi problem with disks of radii 2, 3, and 4 initially stacked
on rods 3, 1, and 3 respectively. All disks can be moved to rod 1 in 6 steps as illustrated by Figure D.1.
Figure D.1: 6 steps to move all disks to rod 1. The shaded rod represents the rod moved on the last step.
The second operation requires you to solve the Tower of Hanoi problem with disks of radii 1, 2, and 3 initially stacked
on rods 2, 3, and 1 respectively.
The fourth operation requires you to solve the Tower of Hanoi problem with disks of radii 2, 3, and 4 initially stacked
on rods 3, 3, and 3 respectively.
The 2025 ICPC Asia Pacific Championship Problem D: Tower of Hanoi