CF498D Traffic Jams in the Land

有一个国家包含 $n+1$ 个城市，这些城市沿一条直线公路依次排列。我们用连续的整数 $1$ 到 $n+1$ 为这些城市编号，编号顺序与城市在公路上的排列一致。因此，城市之间由 $n$ 段公路连接，第 $i$ 段公路连接第 $i$ 个城市和第 $i+1$ 个城市。每一段公路都有一个正整数 $a_{i} > 1$，表示该段公路发生交通拥堵的周期。 为了从城市 $x$ 到城市 $y$（$x < y$），某些司机会采用如下策略： 司机一开始在城市 $x$，当前时间 $t$ 设为 $0$。在到达城市 $y$ 之前，他重复以下操作： - 如果当前时间 $t$ 是 $a_{x}$ 的倍数，则第 $x$ 段公路正处于交通拥堵状态，司机会在当前城市多等待一单位时间（即 $t = t + 1$）。 - 如果当前时间 $t$ 不是 $a_{x}$ 的倍数，则第 $x$ 段公路畅通，司机会花费一单位时间前往城市 $x+1$（即 $t = t + 1$ 且 $x = x + 1$）。 你正在开发一个新的交通管理系统，需要依次处理 $q$ 个查询，查询分为两种类型： 1. 查询从城市 $x$ 到城市 $y$（$x < y$）所需的最终时间 $t$，假设采用上面描述的策略（注意，每次查询都将 $t$ 重置为 $0$）。 2. 将第 $x$ 段公路的拥堵周期替换为 $y$（即 $a_x = y$）。 请你编写程序高效地处理上述所有查询。

第一行包含一个整数 $n$，表示连接 $n+1$ 个城市的公路段数（$1 \leq n \leq 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每一段公路的交通拥堵出现周期（$2 \leq a_i \leq 6$）。 第三行包含一个整数 $q$，表示需要处理的查询数（$1 \leq q \leq 10^5$）。 接下来 $q$ 行每行给出一个查询，格式为 $c, x, y$（$c$ 表示查询类型）。 如果 $c$ 是字符 'A'，表示第一类查询，满足 $1 \leq x < y \leq n+1$。 如果 $c$ 是字符 'C'，表示第二类查询，满足 $1 \leq x \leq n$，$2 \leq y \leq 6$。

对于每一个第一类查询，输出一个整数，表示从城市 $x$ 到城市 $y$ 所需的最终时间 $t$。按输入顺序依次输出结果。

由 ChatGPT 5 翻译