P16799 [蓝桥杯 2026 国 B] 实验数据

小蓝正在帮助老师统计实验数据。 一共有 $n$ 次实验，第 $i$ 次实验的参数为 $i$，对应的实验数据为 $a_i$。为了分析实验参数与实验数据之间的关系，小蓝需要多次查询某个连续区间内实验数据的平均值。为了衡量实验结果的稳定性，他还需要查询该区间内实验数据的方差。 此外，小蓝可能会重新进行某一次实验。若重新进行了第 $k$ 次实验，则原来的 $a_k$ 会被替换为新的实验数据。 对于一次区间查询 $[l, r]$，记区间长度为 $\textit{len} = r - l + 1$，区间平均值为 $$\bar{a} = \frac{\sum_{i=l}^r a_i}{\textit{len}}.$$ 本题中，区间方差定义为 $$\mathrm{Var} = \sum_{i=l}^r (a_i - \bar{a})^2.$$ 你需要支持两类操作： - 查询区间 $[l, r]$ 的平均值与方差； - 将某个位置 $k$ 的实验数据修改为 $x$。 由于答案可能是有理数，为避免精度误差，所有查询结果均在模 $998244353$ 的意义下输出。 具体地，设某个答案为有理数 $x$。将 $x$ 表示为最简分数 $$x = \frac{p}{q},$$ 其中 $p$ 和 $q$ 为整数，$q > 0$，且 $\gcd(p, q) = 1$。本题保证 $q$ 与 $998244353$ 互质。 请输出一个整数 $y$，满足 $$ \begin{aligned} 0 \le y < 998244353, y \equiv p \cdot q^{-1} \pmod{998244353}, \end{aligned} $$ 这里的 $q^{-1}$ 表示 $q$ 在模 $998244353$ 意义下的乘法逆元。

第一行包含两个正整数 $n, m$，分别表示实验次数和操作次数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示初始实验数据。 接下来 $m$ 行，每行描述一个操作，格式为以下两种之一： - `1 l r`：查询区间 $[l, r]$ 内实验数据的平均值和方差； - `2 k x`：将 $a_k$ 修改为 $x$。

对于每个 `1 l r` 操作，输出一行两个整数，分别表示区间平均值和区间方差在模 $998244353$ 意义下的结果。两个结果均按照上述有理数取模规则输出。

### 【样例说明】 第一次查询区间 $[1, 3]$，数据为 $1, 3, 2$，平均值为 $2$，方差为 $$ (1 - 2)^2 + (3 - 2)^2 + (2 - 2)^2 = 2. $$ 第二次查询区间 $[2, 4]$，数据为 $3, 2, 4$，平均值为 $3$，方差为 $2$。随后将 $a_3$ 修改为 $5$，序列变为 $1, 3, 5, 4$。 第三次查询区间 $[1, 3]$，平均值为 $3$，方差为 $8$。 第四次查询区间 $[2, 4]$，平均值为 $4$，方差为 $2$。 ### 【评测用例规模与约定】 对于 $50\%$ 的数据，保证 $n, m \le 3000$。 另有 $20\%$ 的数据，不存在操作 `2 k x`。 对于所有数据，保证： - $1 \le n, m \le 3 \times 10^5$； - $0 \le a_i, x \le 998244353$； - 对于所有查询操作，$1 \le l \le r \le n$； - 对于所有修改操作，$1 \le k \le n$。