P5142 Interval Variance

The problem setter is not able to write an interesting statement...

For a sequence of length $n$, $a_1,a_2,a_3\cdots a_n$, we define its mean $a$ as: $$a=\frac{1}{n}\sum_{i=1}^{n}a_i$$ and define its variance $d$ as: $$d=\frac{1}{n}\sum_{i=1}^{n}(a_i-a)^2$$ Now you are given a sequence $b_1,b_2\cdots b_n$ of length $n$. You need to support two operations. Each operation has the format `c x y`. If $c=1$, it is an update: set $b_x$ to $y$. If $c=2$, it is a query: compute the variance of $b_x$ through $b_y$ (inclusive). To avoid floating-point errors, output the result as a fraction modulo (mod $1000000007$ ($10^9+7$)).

The first line contains two integers $n,m$, meaning the sequence $b$ has length $n$ and there are $m$ operations. The second line contains $n$ integers $b_i$, representing the initial values of sequence $b$. Then there are $m$ lines, each in the format `c x y`, with meanings as described above. All operations are guaranteed to be valid.

For each operation $2$, output one line.

#### Explanation for Sample 1 After four updates, the sequence $b$ is: $\{1,2,3,4\}$. The variance of interval $[1,1]$ is $0$. The variance of interval $[1,2]$ is $\frac{1}{4}$. The modular inverse of $4$ is $250000002$. The variance of interval $[1,3]$ is $\frac{2}{3}$. The modular inverse of $3$ is $333333336$, and $2\times333333336\bmod M=666666672$. #### Constraints - For $50\%$ of the testdata, $n\leq 1000$, $m\leq 1000$. - For $100\%$ of the testdata, $1\leq n,m\leq 1\times 10^5$, $1\leq b_i\leq 1\times 10^9$, $1\leq x\leq n$. For operation $1$, $1\leq y\leq 1\times 10^9$. For operation $2$, $x\leq y\leq n$. Translated by ChatGPT 5