套路的数据结构

1

给定长度为 \(n\) 的序列 \(a,b\)。两种操作：

1. 询问区间 \([l,r]\)，查询 \(\max\limits_{i=l}^{r}{\{a_i\times b_i\}}\)
2. 给定 \(l,r,v\)，区间 \(\forall i\in[l,r]\)，\(b_i\gets b_i +v\)。

分块。

修改：整块维护块内最值、李超线段树（维护若干个斜率为 \(a_i\) 、截距为 \(a_i\times b_i\) 的直线）、加法 \(\text{tag}\)。

整块：查询 \(x=(\text{tag}+v)\) 的极值，更新块内最值、\(\text{tag}\)。

散块，pushdown 加法 \(\text{tag}\)，重构该块。

查询：平凡。

块长取 \(O(\sqrt n)\)。时间复杂度为 \(O(m\sqrt n\log n)\)。