[CF1540E - Tasty Dishes](https://codeforces.com/problemset/problem/1540/E)
CF1540E - Tasty Dishes
题目大意
给定序列\(a_i\)，保证\(|a_i|\leq i\)
以及一个变换：
\(\displaystyle a_i\leftarrow \sum_{j\in S_i} \max\{a_j,0\}\cdot j+\left\{\begin{aligned} a_i && a_i\leq 0 \\ i\cdot a_i && a_i>0\end{aligned}\right.\)，并且保证\(\forall j\in S_i,j>i\)
要求维护\(q\)个操作：
1.查询在初始值上进行\(k\)轮变换后，\(\sum_{i=l}^r a_i\)的值
2.修改初始值，令\(a_i\leftarrow a_i+x\)，保证\(x\ge 0\)
分析
操作分析
首先观察变换的过程和修改操作，容易发现：
1.每个数\(a_i\)在第一个\(>0\)的时刻开始贡献转移，设这个时间为\(d_i\)
2.当一个数\(a_i\leftarrow a_i+a_j\cdot j (a_j>0)\)，由于\(a_i\ge -i\)，新的\(a_i\)一定\(>0\)
3.只有\(a_i\leq 0,a_i+x>0\)的情况，修改操作会对\(d_i\)产生影响
那么实际上我们可以在每个\(a_i\leq 0,a_i+x>0\)的修改时重构，由于只有\(n\)次重构，这一部分复杂度为\(O(n^3)\)
设转移矩阵\(A_{i,j}=[j\in S_i\ or\ j=i] \cdot j\)
设\(e_i\)为一个只有第\(i\)项为\(1\)的列向量
若\(k\ge d_i\)，则我们要求\(\sum A^{k-d_i} e_i a_i\)
固然不能每次都求矩阵幂，即便是预处理之后用\(O(n^2\log k)\)的复杂度依然不可取
加速矩阵幂
考虑到给定矩阵的特殊性，考虑用 矩阵特征值 来优化
由于\(A\)是一个上三角矩阵，那么一定满足\(A_{i,i}\)都是其特征值，而这题限定了\(A_{i,i}=i\)
故\(A\)有\(n\)个特征值，并且由于\(A\)是上三角矩阵，可以在\(O(n^3)\)时间消元得到每个\(i\)对应的特征向量\(v_i\)
模拟这个过程也容易发现，\(v_i\)构成的矩阵\(\begin{bmatrix} \array{v_1 & v_2 &\cdots &v_n}\end{bmatrix}\)是一个上三角矩阵
在所求的式子中并不存在有关\(v_i\)的表达式，但是有列向量\(e_i\)，并且\(v_i\)线性无关
因此我们以\(n\)个\(v_i\)作为基底替换\(c\)，构造矩阵\(c\)，满足\(e_i=\sum c_{i,j} v_j\)
形式化的，就是
\(c \cdot \begin{bmatrix} \array{&&v_1^T &&\\ && v_2^T &&\\ &&\cdots&& \\ &&v_n^T&&}\end{bmatrix}=\begin{bmatrix} \array{&&e_1^T &&\\ && e_2^T &&\\ &&\cdots&& \\ &&e_n^T&&}\end{bmatrix}\)
而右边是一个单位矩阵，故实际上这个操作就是求矩阵逆，而这个矩阵是满秩的
此时，答案式子替换为\(\displaystyle \sum A^{k-d_i}\sum c_{i,j}v_ja_i\)，再带入特征值的定义\(Av_i=iv_i\)
转化为\(\displaystyle \sum a_i \sum j^{k-d_i}c_{i,j}v_j\)
我们可以预处理\(v_{j,k}\)的前缀和，容易求得\(v_{j,[l,r]}\)
再将\(k-d_i\)参数分离，只需要维护\(s_j=\sum_i a_i c_{i,j} j^{-d_i}\)，所有的幂次均可以预处理得到
由于不一定满足\(k\ge d_i\)，因此需要用数据结构维护前缀和，复杂度为\(O(qn\log n)\)
如果线性预处理树状数组，则重构总复杂度为\(O(n^3)\)
1 | const int N=310,INF=1e9+10,P=1e9+7; |