U435624 【模板】KTT

出自 [2020 年集训队论文](https://rusunoi.github.io/books/National-Team-Thesis/2020.pdf)。

现有 $n$ 个一次函数形成一个序列，序列上每个位置都是 $a_i \times x_i + b_i$。 你需要支持以下操作： - $1 \ \ \ l \ \ \ r \ \ \ k$：将区间 $l$ 到 $r$ 的 $x_i$ 增加 $k$，**其中 $k > 0$**。 - $2 \ \ \ l \ \ \ r$：询问区间 $l$ 到 $r$ 的**最大值**。 共有 $m$ 个操作。

> $n$ $\space \space$ $m$ > > $a_1,b_1$ > > $a_2,b_2$ > > $\vdots$ > > $a_n,b_n$ > > $1 \space l_1 \space r_1 \space k_1 \space or \space 2 \space l_1 \space r_1$ > > $1 \space l_2 \space r_2 \space k_2 \space or \space 2 \space l_2 \space r_2$ > > $\vdots$ > > $1 \space l_n \space r_n \space k_n \space or \space 2 \space l_n \space r_n$

对于每个询问，一行一个正整数表示答案。

$1 \le n,m \le 10^5$，$1 \le a_i,b_i \le 10^9$，$1 \le k_i \le 100$。 本题没有验题人，std 是出题人用从过了的使用了 ktt 的题目中封装起来的 ktt 写的，如有出错请联系出题人。 [题解](https://www.cnblogs.com/cndarkmoon/articles/18216427)