线段树维护平均数与方差

题目描述

维护一个长度为$n$序列$ai$，支持$3$种操作共$m$次:

1. 给定区间$[l,r]$ 以及 $x$，给 $[a_l...a_r]$ 都加上$x$
2. 给定区间$[l,r]$，求出区间 $[a_l...a_r]$ 的均值 $a= \frac{1}{r−l+1} \sum^{r}_{i=l}a_i$
3. 给定区间$[l,r]$，求出区间 $[a_l...a_r]$ 的方差$D= \frac{1}{r−l+1} \sum^{r}_{i=l}(a_i - \overline{a})^{2}$

输入格式

第一行包含两个正整数 $N,M$，分别表示数列中实数的个数和操作的个数。

第二行包含 $N$ 个实数，其中第 $i$ 个实数表示数列的第 $i$ 项。

接下来 $M$ 行，每行为一条操作，格式为以下三种之一：

操作 $1$：1 x y k ，表示将第 $x$ 到第 $y$ 项每项加上 $k$，$k$ 为一整数。
操作 $2$：2 x y ，表示求出第 $x$ 到第 $y$ 项这一子数列的平均数。
操作 $3$：3 x y ，表示求出第 $x$ 到第 $y$ 项这一子数列的方差。

数据范围:

$n,m≤10^5,x≤10^9$, 结果对 $10^9+7$ 取 $mod$

输出格式

输出包含若干行，每行为一个实数，

样例 #1

样例输入 #1

3 5
9 10 6 2 3 3
2 3 3
1 2 3
9
3 2 3
3 1 1

样例输出 #1

6
6
4
0