P6108 [Ynoi2009] rprsvq

你有一个长度为 $n$ 的序列 $v_1, v_2, \dots, v_n$，初值全都为 $0$。 你要进行 $m$ 次操作： - 操作 1：给出 $l,r,a$，将 $v_l,v_{l+1},\dots ,v_r$ 的值加上 $a$。 - 操作 2：给出 $l,r$，求在$v_l,v_{l+1}, \dots ,v_r$ 中选出一个非空的子序列，求所有方案中选出的子序列的方差之和，答案对 $998244353$ 取模。 一个序列 $a_1,a_2, \dots, a_n$ 的方差定义为令 $\bar{a}=\frac{1}{n}\sum_{i=1}^n a_i$，则方差为 $\frac{1}{n}\sum_{i=1}^n (a_i-\bar{a})^2$。

无

无

Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078 对于 $10\%$ 的数据，$n\leq 10, m\leq 1000$。 对于 $20\%$ 的数据，$n\leq 16, m\leq 1000$。 对于 $30\%$ 的数据，$n\leq 100, m\leq 10^3$。 对于 $50\%$ 的数据，$n, m\leq 10^3$。 对于另外$10\%$的数据，$n\leq 10^5$，保证首先是第一类操作，然后是第二类操作。 对于 $80\%$ 的数据，$n, m\leq 10^5$。 对于 $100\%$ 的数据，$1\leq n \leq 5\times 10^6,1\leq m\leq 10^5$。 对于第一个测试数据的第一个询问，序列是 $\{0,1,1\}$，所有的子序列中只有 $\{0,1\}, \{0,1\}$ 和 $\{0,1,1\}$ 方差不为 $0$，分别是 $\frac{1}{4}, \frac{1}{4}, \frac{2}{9}$，总和为 $\frac{13}{18}$。