#P2122. 还教室

还教室

题目背景

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

题目描述

在接受借教室请求的 nn 天中,第 ii 天剩余的教室为 aia_i个。作为大学借教室服

务的负责人,你需要完成如下三种操作共 mm 次:

① 第 ll 天到第 rr 天,每天被归还 dd 个教室。

② 询问第 ll 天到第 rr 天教室个数的平均数。

③ 询问第 ll 天到第 rr 天教室个数的方差。

输入格式

第一行包括两个正整数 nnmm,其中 nn 为借教室的天数,mm 为操作次数。

接下来一行,共包含 nn 个整数,第ii个整数表示第 ii 天剩余教室数目为 aia_i个。

接下来 mm 行,每行的第一个整数为操作编号(只能为 112233),接下来:

包含两个正整数 llrr,若操作编号为 11,则接下来再包含一个正整数 dd

输出格式

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

5 4
1 2 3 4 5
1 1 2 3
2 2 4
3 2 4
3 1 5
4/1
2/3
14/25

提示

对于全部测试数据满足:1lrn105,m1051 \leq l \leq r \leq n \leq 10^5, m\leq 10^50ai100 \leq a_i \leq 101d31 \leq d \leq 3,操作 11 的数量不超过 10%10\%

注意:aia_idd 的范围很小及操作 11 数量很少的原因是为了保证答案的分子不会很大,以防止答案的分子溢出 6464 位整数的范围,这与题目做法无关。