还教室

还记得 NOIP 2012 提高组 Day2 中的借教室吗?时光飞逝,光阴荏苒,两年 过去了,曾经借教室的同学们纷纷归还自己当初租借的教室。请你来解决类似于 借教室的另一个问题。

「问题描述」

在接受借教室请求的 n 天中,第 i 天剩余的教室为 ai 个。作为大学借教室服 务的负责人,你需要完成如下三种操作共 m 次:

1 第l天到第r天,每天被归还d个教室。 2 询问第 l 天到第 r 天教室个数的平均数。 3 询问第 l 天到第 r 天教室个数的方差。

「输入格式」

第一行包括两个正整数 n 和 m,其中 n 为借教室的天数,m 为操作次数。 接下来一行,共包含 n 个整数,第 i 个整数表示第 i 天剩余教室数目为 ai 个。 接下来 m 行,每行的第一个整数为操作编号(只能为 1 或 2 或 3),接下来

包含两个正整数 l 和 r,若操作编号为 1,则接下来再包含一个正整数 d。 「输出格式」

对于每个操作 2 和操作 3,输出一个既约分数(分子与分母互质)表示询问 的答案(详见样例)。若答案为 0,请输出“0/1”(不含引号)。

「样例输入」

54
1 2345 1 123 2 24
3 24
3 15

「样例输出」

4/1 2/3 14/25

「样例说明」

初始情况下,剩余教室数量为(1, 2, 3, 4, 5)。 第1次操作为第1天到第2天归还3个教室,变为(4, 5, 3, 4, 5)。

第2次操作询问第2天到第4天的平均数为5+3+4 = 4。 31

第3次操作询问第2天到第4天的方差为1+1+0 = 2。 33

第4次操作询问第1天到第5天的方差为 0.04 + 0.64 +1.44 + 0.04 + 0.64 = 14 。 5 25

「数学小贴士」

1n 1n n个数的平均数为x= ∑x,n个数的方差为 ∑(x−x)2。

「数据规模与约定」

n,m<=100000

只要用线段树维护区间和以及区间平方和T T

然后推推公式神马的