我们容易想到预处理区间 \([l, r]\) 中的 \(m_a \times m_b\)。
这样算出来的是一个二维的矩阵，每次的答案就是红色部分：
但是这样的问题是二维的，无论如何都不是正解。
考虑把列这一维压掉，也就是令 \(w'_i \leftarrow w_{i,i} + w_{i,i+1} + ... + w_{i,r}\)。
这样询问的答案就是一个序列求和了，就可能可以用线段树啥的来维护。
但是你发现线段树查询时能够约束的条件只有一维：\(L\)，所以对于\(R\)，我们需要通过枚举的顺序来保证 \(R\) 的限制，一个直观的做法将询问离线，按照 \(R\) 排序。
每次加入一个新的 \(R\)，会多出一个 \(w_{i,R}\)。更新 \(w'\)的时候发现从下面算到上面，就能够\(O(n^2+qn)\)求解此问题了。
于是拿下\(20 pts\)。
发现\(w'\)都是加上一个数，这就提示我们寻找哪些区间具体加上了哪些数。
于是你直接输出每次的 \(m_a\) ，打表找规律。
找那种规律明显的，比如29 29 29 29 29 30 ...。29就是a[R]。
非常明显了：一个数左边第一个大于等于它的数为a[pa[R]]，那么在\([pa[R]+1, R]\)，\(m_a\)都是\(a[R]\)。
在此之前的 \(m_a\) 就还是原来的数，不变。
这个位置可以单调栈求解。
这时候我们就发现有些复杂了，因为有a和b，pa[R]和pb[R]不一定相等。这时候我们一般先考虑一个序列，再考虑加上另一个序列的影响。比如这里先假设b的最大值没有变化。
题目直接需要维护的信息是\(w'\)的和，记为\(sw\)。
在\([pa[R]+1, R]\)的情况中，如果一个区间完全被包含，\(sw \leftarrow a[R] \times m_b[R] + a[R] \times m_b[R-1] + ...\)，记\(smb\)为区间中所有\(i\)，\([i,r]\)中\(m_b\)的和，那么\(sw \leftarrow sw + smb \times k\)。
在\([1, pa[R]]\)的情况中，最大值没有变化，我们多加的那一部分，其实就是枚举到\(R-1\)时多加的那一部分，记为\(xy\)，全部\(xy\)的和\(sxy\)。\(sw \leftarrow sw + sxy\)。
现在来考虑b的影响，在\([1, pb[R]]\)，b的最大值没变化，相当于没有影响。
在\([pb[R]+1, R]\)，b的最大值都是\(b[R]\)，消去在\([pa[R]+1, R]\)的情况中的影响，然后加上新的贡献。
\(sw \leftarrow sw - sxy + sma \times b[R]\)。
可以先模拟一下信息的维护，防止推导出错。
CODE。
然后你发现要维护
\[\begin{bmatrix} sw & sma & smb & sxy & len \end{bmatrix} \]求出对应的系数矩阵就行了。
常数太大挂掉了……
这个时候我们就要优化矩阵乘法，详见这里。
需要注意，不是说标记矩阵最初某个位置上是常量，它就一定是常量。
这个时候就是把所有操作统一起来，看下哪些位置上是变量。
然后写个程序，将常量（所有操作最初的系数矩阵中的常量）赋值为它对应的数，变量赋值为随机数，然后多乘几次，如果某个位置上的值一直不变，就可以认为它是常量了。
当然你也可以每一个位置去手算，但是这样太慢了。
箭头指出来的地方本来是常量，但是乘几次之后就不是了……
给它们标好序号，也就是\(v_0,...\)。
每次算的时候一行行算，把每一个列对应抄出来，然后对应乘。
比如算\(v_3\)：
算\(v_4\)的时候，把列擦掉，行不用变，然后一样去算，这样正确率比较高。
信息矩阵一样的方法优化。
标签：比赛,leftarrow,矩阵,sw,29,times,pa,NOIP2022,P8868 From： https://www.cnblogs.com/zhangchenxin/p/17796538.html