← 返回题目列表

Codeforces · 498/D

D. 陆地上的交通拥堵

中文机器翻译题面 查看原题

某个国家由 (n + 1) 个城市组成,位于一条笔直的高速公路沿线。让我们按照城市沿高速公路出现的顺序,使用从 1 到 n + 1 的连续整数对城市进行编号。因此,城市由 n 段高速公路连接,第 i 段连接城市编号 i 和 i+1。高速公路的每一段都与一个正整数 ai > 1 相关联 - 其上出现交通拥堵的时间段。

为了从城市 x 到城市 y (x < y),一些司机使用以下策略。

最初,驾驶员位于城市 x,当前时间 t 为零。直到司机到达y城市,他执行以下操作:

- 如果当前时间 t 是 ax 的倍数,则编号为 x 的高速公路路段现在出现交通问题,并且驾驶员在当前城市停留了一个单位时间(形式上来说,我们指定 t = t + 1);
- 如果当前时间 t 不是 ax 的倍数,则高速公路编号 x 的路段现在是清晰的,这就是驾驶员使用一个单位时间移动到城市 x + 1 的原因(正式地,我们指定 t = t + 1 和 x = x + 1)。

您正在开发一种新的交通控制系统。您想要连续处理两种类型的 q 个查询:

1. 假设我们应用上述策略,确定从城市 x 骑行到城市 y 后时间 t 的最终值 (x < y)。请注意,对于每个查询,t 都会重置为 0。
2. 将路段号 x 上出现的交通拥堵周期替换为值 y(形式上,指定 ax = y)。

编写一段代码来有效处理上面给出的查询。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 连接 n + 1 个城市的高速公路路段数。

第二行包含 n 个整数 a1, a2, ..., an (2 ≤ ai ≤ 6) — 高速公路路段出现交通拥堵的周期。

下一行包含一个整数 q (1 ≤ q ≤ 105) — 要处理的查询数。

接下来的 q 行包含格式为 c, x, y 的查询描述(c — 查询类型)。

如果 c 是字符“A”,那么您的任务是处理第一种类型的查询。在这种情况下,满足以下约束:1 ≤ x < y ≤ n + 1。

如果c是字符“C”,那么您需要处理第二种类型的查询。在这种情况下,满足以下约束:1 ≤ x ≤ n,2 ≤ y ≤ 6。

输出

对于第一种类型的每个查询,输出一个整数——从城市 x 开车到城市 y 后时间 t 的最终值。按照输入中给出的顺序处理查询。

示例

输入 #1

10
2 5 3 2 3 5 3 4 2 4
10
C 10 6
A 2 6
A 1 3
C 3 4
A 3 11
A 4 9
A 5 6
C 7 3
A 8 10
A 2 5

输出 #1

5
3
14
6
2
4
4