P6108 [Ynoi2009] rprsvq

You have a sequence $v_1, v_2, \dots, v_n$ of length $n$, with all initial values equal to $0$. You need to perform $m$ operations: - Operation 1: Given $l, r, a$, add $a$ to $v_l, v_{l+1}, \dots, v_r$. - Operation 2: Given $l, r$, choose a non-empty subsequence from $v_l, v_{l+1}, \dots, v_r$. For all possible choices, compute the sum of variances of the chosen subsequences. Output the answer modulo $998244353$. The variance of a sequence $a_1, a_2, \dots, a_n$ is defined as follows. Let $\bar{a}=\frac{1}{n}\sum_{i=1}^n a_i$, then the variance is $\frac{1}{n}\sum_{i=1}^n (a_i-\bar{a})^2$.

The first line contains two integers $n, m$. The next $m$ lines describe the operations. Each line contains either four integers $1~l~r~a$ or three integers $2~l~r$, representing an operation of the first type or the second type. It is guaranteed that $0\leq a< 998244353$.

For each operation of the second type, output one line containing the answer.

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078. Constraints: For $10\%$ of the testdata, $n\leq 10, m\leq 1000$. For $20\%$ of the testdata, $n\leq 16, m\leq 1000$. For $30\%$ of the testdata, $n\leq 100, m\leq 10^3$. For $50\%$ of the testdata, $n, m\leq 10^3$. For another $10\%$ of the testdata, $n\leq 10^5$, and it is guaranteed that all operations of the first type come first, followed by operations of the second type. For $80\%$ of the testdata, $n, m\leq 10^5$. For $100\%$ of the testdata, $1\leq n \leq 5\times 10^6, 1\leq m\leq 10^5$. For the first query in the first testdata, the sequence is $\{0,1,1\}$. Among all subsequences, only $\{0,1\}$, $\{0,1\}$, and $\{0,1,1\}$ have non-zero variance, which are $\frac{1}{4}, \frac{1}{4}, \frac{2}{9}$ respectively. Their total sum is $\frac{13}{18}$. Translated by ChatGPT 5