U390630 分考场 (部分蓝桥杯官方数据+自造数据)

古语有云：春风得意马蹄疾，一日看尽长安花。当然在一场考试中所有人都春风得意马蹄疾是不可能的，尤其是碰到一些毒瘤出题人的时候。 又到了每月一次的月考，又是 $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$ 位小数**。 **误差不超过 $0.003$,已开 $Special Judge$**。

**【样例说明】**\ **第一个操作**询问学号在 $[1,4]$ 之间的同学分成 $3$ 个考场的平均分的平均分的最大值，最优策略是：$\{1\},\{2, 4\},\{3\}$，平均分是 $\dfrac{\dfrac{5}{1} +\dfrac{3+2}{2} + \dfrac{4}{1}}{3}$ 。\ **第二个操作**把学号为 $4$ 的同学的分数变为 $8$。\ **第三个操作**询问学号在 $[3, 5]$ 之间的同学分成 $3$ 个考场的平均分的平均分的最大值，最优策略是：$\{3\},\{4\}, \{5\}$。\ **第四个操作**把学号为 $2$ 的同学分数变为 $2$。 第五个操作询问学号在 $[1, 3]$ 之间的同学分成 $2$ 个考场的平均分的平均分 的最大值，**最优策略是：$\{1\},\{2,3\}$**。 **附件为测试点2的数据** **【评测用例规模与约定】** 对于全部评测用列，$n \le 200000$,$q \le 200000$, **任意时刻同学的分数 $v_i \le 2147483647$， $k \le r- l + 1$。** \ **由于官方数据为 $2e5$ 级别,空间 $1024MB$ 很可能不够,所以增加限制,保证出现的不同数字数目不超过 $2e5$,换句话说,离散化后(这里包括原数组数字以及修改中出现的新数字)的数据规模不会超过 $2e5$**。 $$Subtask0:n,q \le 200,10\ 分,时限\ 1s$$ $$Subtask1:n,q \le 2000,\ 20分,时限\ 1s$$ $$Subtask2:n,q \le 50000,\ 30分,时限\ 3s$$ $$Subtask3:n,q \le 100000,\ 20分,时限\ 5s$$ $$Subtask4:n,q \le 200000,20分,时限\ 10s$$ **并且保证离散化数组 $a$ 与修改出现的 $v_i$ 的不同数字数量不超过 $2e5$,即所有的 $a_i$与 $v_i$ 组成的集合中不同的数的数目不超过 $2e5$。**