CF311D Interval Cubing

在学习计算几何的过程中，Tiny 同时正在学习一种叫做线段树的数据结构。他刚刚掌握这种数据结构，便遇到了一个奇怪的问题： 给定一个整数序列 $a_1, a_2, \ldots, a_n$。你需要处理 $q$ 个操作，操作分为两种类型： 1. 给定两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$），询问序列 $a_l, a_{l+1}, \ldots, a_r$ 中所有元素的和。 2. 给定两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$），将区间 $a_l, a_{l+1}, \ldots, a_r$ 中的每个元素 $x$ 替换为 $x^3$，也就是执行 $a_l = a_l^3, a_{l+1} = a_{l+1}^3, \ldots, a_r = a_r^3$。 对于每个类型为 1 的操作，输出对应的答案。 Tiny 当然无法自己解决这个问题，所以他向你寻求帮助。此外，Tiny 非常喜欢质数。他告诉你，由于答案可能非常大，请将每次查询的结果对 $95542721$（这是一个质数）取模后输出。

第一行包含一个整数 $n$（$1 \leq n \leq 10^{5}$），表示序列的长度。 第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$）。 第三行包含一个整数 $q$（$1 \leq q \leq 10^{5}$），表示操作的数量。接下来的 $q$ 行，每行包含三个整数 $t_i$（$1 \leq t_i \leq 2$）、$l_i$、$r_i$（$1 \leq l_i \leq r_i \leq n$）。其中 $t_i$ 表示操作类型，$l_i$ 和 $r_i$ 分别为该操作的参数。

对于每个类型 1 的操作，输出一个答案，每行一个。 请注意，输出的每个数均应为非负且小于 $95542721$。

由 ChatGPT 5 翻译