给定两个长度为 \(n\) 的数列 \(a\) 和 \(b\)，有 \(m\) 个操作，操作分为三类：
\(1\) \(l\) \(r\) \(w\) ：将数列 \(a\) 中区间 \([l,r]\) 内所有数加上 \(w\) ;
\(2\) \(x\) \(y\) ：交换 \(b_x\) 和 \(b_y\) ;
\(3\) \(l\) \(r\) ： 求 \(\displaystyle \max_{i=l}^r \{a_i\cdot b_i\}\) .
\(1\le n,m\le 10^5,\ 0\le a_i\le 10^7,\ 0\le b_i\le 10^5,\ 0\le w_i\le 100\) .
考虑分块。每一块就直接维护 max{\(a_i\cdot b_i\)} .
然后我们看操作。第二个操作十分简单，直接交换后暴力重构即可。第一个操作区间修改，两边的块也可以直接修改。关键在于中间的块。
我们要求的元素的权值 \(w_i=cnt\cdot b_i+c_i\). \( \(cnt\) 为整块累加的值, \(c_i=a_i\cdot b_i\))
我们发现这其实是一个一次函数。我们对于每个 \(cnt\) 要找到最大的 \(w_i\) .
我们考虑对上面的式子变形，得到： \(c_i=-cnt\cdot b_i+w_i\).
我们要求的 \(w_i\) 即为斜率为 \(-cnt\) 的直线经过所有 \((b_i,c_i)\) ，与y轴的截距。显然最大截距的直线一定是凸壳的一条切线。同时我们发现随着 \(cnt\) 的增大，最大值的点的位置单调向右移动。
这样我们对于每一块按 \(b\) 值排序，然后维护一个上凸壳。每次整块增加时直接打标记，然后向右移动最大值位置。
单次修改复杂度为 $ \displaystyle\frac{n}{S}+S\log n$ ， 取块大小 \(S\) 为 \(\displaystyle \sqrt{\frac{n}{\log n}}\) 复杂度最优为 \(O(\sqrt{n\log n})\)
原文：https://www.cnblogs.com/farway17/p/10425636.html