E-速度即转发_牛客挑战赛48

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

BPM=RT

给定正整数 $n$ ，和非负整数组成的参数序列 $a_1,a_2,\dots,a_n$ 。

进行 $m$ 次操作。

操作包含以下两种：

查询速度：给定 $l,r,k$ ，设 $S(x) = \sum\limits_{i=l}^r \max(a_i-x,0)$ ，求 $[0,10^5]$ 内满足 $S(x) \ge k$ 的最大的整数 $x$ 。
转发：给定 $p,k$ ，将 $a_p$ 修改为 $k$ 。

第一行，两个正整数 $n,m$ 。
第二行， $n$ 个非负整数 $a_1,a_2,\dots,a_n$ 。
以下 $m$ 行，每行第一个整数 $\rm op$ 表示操作的类型。

若 ${\rm op} = 0$ ，则接下来有三个整数 $l,r,k$ ，表示一个查询速度操作。

若 ${\rm op} = 1$ ，则接下来有两个整数 $p,k$ ，表示一个转发操作。

对于每个查询操作，一行一个整数，表示答案。若在  内无解，输出 。

示例1

复制

6 5
4 42 40 26 46 6
0 1 5 20
1 6 4
0 2 6 20
0 2 6 114514
0 1 6 0

复制

，；修改操作满足 ，；查询操作满足 ，。