题目背景

古语有云：春风得意马蹄疾，一日看尽长安花。

当然在一场考试中所有人都春风得意马蹄疾是不可能的，尤其是碰到一些毒瘤出题人的时候。

又到了每月一次的月考，又是 xf 老师出题。

上一次 xf 老师出的题太毒瘤了，平均分只有 $40$ 多，同学们都非常不满意，毕竟别的科的平均分都是 $80$ 多。

题目描述

这次 xf 为了不被同学们寄刀片，想了一个办法：只公布所有考场的平均分的平均分。这样他就可以通过调整考场的分配方式，使得平均分显得高。（每个考场都可以容纳无限人）

每次考试也不是所有同学都参加的，只有学号在 $[l,r]$ 这个区间中的同学会参加。

他想知道对于每次考试，他调整过考场后，所有考场的平均分的平均分的最大值。

当然，同学们也可能会努力学习或整日颓废使成绩发生改变。

输入格式

输入的第一行包含一个整数 $n$。

第二行包含 $n$ 个整数，第 $i$ 个数 $v_i$，表示开始时每个同学的成绩。

第三行包含一个整数 $q$，表示有 $q$ 次操作。之后 $q$ 行，每行描述一个操作，第一个数表示操作类型。

如果操作为 1 p x，表示学号为 $p$ 的同学分数变为 $x$。

如果操作为 2 l r k, 表示把学号在 $[l,r]$ 中的同学分成 $k$ 个考场，求这 $k$ 个考场的平均分的平均分的最大值。

输出格式

对于每个 $2$ 操作输出一行，四舍五入保留正好 $3$ 位小数。

5
5 3 4 2 1
5
2 1 4 3
1 4 8
2 3 5 3
1 2 2
2 1 3 2

3.833
4.333
4.000

提示

【样例说明】

第一个操作询问学号在 $[1, 4]$ 之间的同学分成 $3$ 个考场的平均分的平均分的最大值，最优策略是：$\{1\}$, $\{2, 4\}$, $\{3\}$，平均分是 $(5/1 +(3+2)/2 + 4/1)/3$。

第二个操作把学号为 $4$ 的同学的分数变为 $8$。

第三个操作询问学号在 $[3, 5]$ 之间的同学分成 $3$ 个考场的平均分的平均分 的最大值，最优策略是：$\{3\}$, $\{4\}$, $\{5\}$。

第四个操作把学号为 $2$ 的同学分数变为 $2$。

第五个操作询问学号在 $[1, 3]$ 之间的同学分成 $2$ 个考场的平均分的平均分的最大值，最优策略是：$\{1\}$, $\{2,3\}$。

【评测用例规模与约定】

对于全部评测用列，$1\le n, q \le 200000$，任意时刻同学的分数 $v_i \le 10^9$，$k \le r- l + 1$。

评测时将使用 $20$ 个评测用例测试你的程序，每个评测用例的限制如下：

评测用例编号	$n \le$	$q \le$	特殊说明
1	10	1	无
2,3	100
4,5,6	2000
7,8,9	50000
10,11,12	200000		没有 1 操作
13∼20			无

蓝桥杯 2019 年国赛 A 组 I 题。