争取达到 O(QlogM)O(Q\log M)O(QlogM)~
A1,i =S×A1,i−1+T×i =Si×A1,0+T×∑j=1ij×Si−j+1 =Si×A1,0+T×((S)+(S+S2)+(S+S2+S3)+(S+S2+S3+S4)+...+(S+...+Si))=Si×A1,0+T×∑j=1i∑k=1i−j+1Sk =Si×A1,0+T×∑j=1iSi−j+2−1S−1 =Si×A1,0+TS−1×∑j=1i(Si−j+2−1) =Si×A1,0+TS−1×((∑j=1iSi−j+2)−i) =Si×A1,0+TS−1×((Si+2−iS−1)−i) =Si×A1,0+T(S−1)2×((Si+2−i)−i×(S−1)) =Si×A1,0+T(S−1)2×(Si+2−i×S) A_{1,i}\\\space\\
=S\times A_{1,i-1}+T\times i\\\space\\ =S^i\times A_{1,0}+T\times \sum_{j=1}^{i} j\times S^{i-j+1}\\\space\\\space\\ =S^i\times A_{1,0}+T\times ((S)+(S+S^2)+(S+S^2+S^3)+(S+S^2+S^3+S^4)+...+(S+...+S^i))\\ =S^i\times A_{1,0}+T\times \sum_{j=1}^i\sum_{k=1}^{i-j + 1} S^k\\\space\\ =S^i\times
A_{1,0}+T\times \sum_{j=1}^i \dfrac{S^{i-j+2}-1}{S-1}\\\space\\ =S^i\times A_{1,0}+\dfrac{T}{S-1}\times \sum_{j=1}^i (S^{i-j+2}-1)\\\space\\ =S^i\times A_{1,0}+\dfrac{T}{S-1}\times ((\sum_{j=1}^i S^{i-j+2})-i)\\\space\\ =S^i\times A_{1,0}+\dfrac{T}{S-1}\times ((\dfrac{S^{i+2}-i}{S-1})-i)\\\space\\
=S^i\times A_{1,0}+\dfrac{T}{(S-1)^2}\times ((S^{i+2}-i)-i\times(S-1))\\\space\\ =S^i\times A_{1,0}+\dfrac{T}{(S-1)^2}\times (S^{i+2}-i\times S)\\\space\\ A1,i =S×A1,i−1 +T×i =Si×A1,0 +T×j=1∑i j×Si−j+1 =Si×A1,0 +T×((S)+(S+S2)+(S+S2+S3)+(S+S2+S3+S4)+...+(S+...+Si))=Si×A1,0 +T×j=1∑i k=1∑i−j+1
Sk =Si×A1,0 +T×j=1∑i S−1Si−j+2−1 =Si×A1,0 +S−1T ×j=1∑i (Si−j+2−1) =Si×A1,0 +S−1T ×((j=1∑i Si−j+2)−i) =Si×A1,0 +S−1T ×((S−1Si+2−i )−i) =Si×A1,0 +(S−1)2T ×((Si+2−i)−i×(S−1)) =Si×A1,0 +(S−1)2T ×(Si+2−i×S)
