4090 艾莎

题面

内容

艾莎给你一个长度 $n$ 的序列 $a_1,\dots,a_n$，共 $m$ 次操作，共两种操作类型：

1. 给定 $l,r,x$，将 $a_l,\dots,a_r$ 加上 $x$。
2. 给定 $l,r$，查询 $\mathop{\max}\limits_{l\le L<R\le r}\frac{\sum\limits_{i=L}^R a_i}{R-L+1}$ 。

输入

第一行两个整数 $n,m$ ；

第二行 $n$ 个整数 $a_1,\dots,a_n$ ；

接下来 $m$ 行，每行 $1,l,r,x$ 或 $2,l,r$ 表示一个操作。

输出

对每个操作2，输出一行，包含一个最简分数（形如 a/b 或 -a/b 或 0/1 ； $a,b$ 是互质的正整数）表示答案，例如 $\frac{5}{3},\;-\frac46,\;-1,\;0,\;2$ 分别应输出为 5/3 ， -2/3 ，-1/1 ，0/1 ，2/1。

样例1

输入

5 8
-7 -8 -1 5 8
1 4 5 -3
1 2 3 7
1 5 5 3
1 1 4 1
2 4 5
1 3 4 -1
1 1 2 7
2 4 5

输出

11/2
5/1

提示

对于 $25\%$ 的数据，满足 $n,m\le 100$。

对于 $50\%$ 的数据，满足 $n,m\le 8000$。

对于另外 $25\%$ 的数据，满足 没有操作 $1$。

对于 $100\%$ 的数据，满足 $1\le n,m\le 10^6$，$|a_i|,|x|\le 10^3$，所有数值为整数。对于操作2，保证不存在 $l=r$ 的情况。

思路

只需要维护长度为2和3的最大子段，

线段树维护区间内所有长度为2的连续子段中最大和区间内所有长度为3的连续子段中最大。

因为任意一个区间都可以被分成两段不同的区间，这两个区间的平均值一定有一个大于等于原来的区间，另一个区间的平均值小于等于原来的平均值，所以这么不断去下去，直到剩下三个，那么假如分出来的那一个点比原来的大，但是剩下的两个比原来的小，由于一个点不能独立为一个区间，因此要保留三个。

合并的时候分两种情况讨论，

区间加的时候就分别两倍三倍加。

我们每个区间记录一下左端的两个值和右端的两个值，合并的时候比较一下原来两个区间的最大值和交界处新产生的值比较一下取最大就可以了。

代码

待补。