The 2021 ICPC Asia Nanjing Regional Contest E.Paimon Segment Tree 区间合并线段树/维护矩阵乘法

The 2021 ICPC Asia Nanjing Regional Contest E.Paimon Segment Tree 区间合并线段树/维护矩阵乘法 题目大意

给定长度为 n n n的序列 a 1 , a 2 , … , a n a_1,a_2, \dots, a_n a1​,a2​,…,an​，要求支持区间加操作，同时对操作记录历史版本，查询问区间 [ l , r ] [l,r] [l,r]操作 [ s , t ] [s,t] [s,t]中的每个数的平方之和。

题目思路

推了一会，发现线段树合并硬写很凌乱，然后队友告诉是线段树维护矩阵乘法，那么就考虑怎么维护：

设：

• l e n = r − l + 1 len = r - l + 1 len=r−l+1，区间长度
• s u m 1 sum_1 sum1​，区间和
• s u m 2 sum_2 sum2​，区间平方和
• s u m 3 sum_3 sum3​，区间历史平方和

考虑每次区间加 v a l val val，那么考虑各个数字的变化：

• 对于区间和，变化量就是 l e n × v a l len \times val len×val

• 对于区间平方和： ( ( x 1 + v a l ) 2 + ( x 2 + v a l ) 2 + ⋯ + ( x n + v a l ) 2 ) − ( x 1 2 + x 2 2 + ⋯ + x n 2 ) = ( 2 × x 1 + v a l ) × ( x 1 − x 1 + v a l ) … ( 2 × x 1 + v a l ) × ( x 1 − x 1 + v a l ) = l e n × v a l 2 + 2 × v a l × s u m 1 ((x_1 + val)^2 + (x_2 + val)^2 + \dots + (x_n + val)^2) - (x_1^2 + x_2^2 + \dots + x_n^2) \\= (2 \times x_1 + val) \times (x_1 - x_1 + val) \dots (2 \times x_1 + val) \times (x_1 - x_1 + val)\\ =len \times val^2 + 2 \times val \times sum_1 ((x1​+val)2+(x2​+val)2+⋯+(xn​+val)2)−(x12​+x22​+⋯+xn2​)=(2×x1​+val)×(x1​−x1​+val)…(2×x1​+val)×(x1​−x1​+val)=len×val2+2×val×sum1​

那么就有：

• l e n = l e n len = len len=len
• s u m 1 = s u m 1 + l e n × v a l sum_1 = sum_1 + len \times val sum1​=sum1​+len×val
• s u m 2 = s u m 2 + 2 × v a l × s u m 1 + l e n × v a l 2 sum_2 = sum_2 + 2 \times val \times sum_1 + len \times val^2 sum2​=sum2​+2×val×sum1​+len×val2
• s u m 3 = s u m 3 + s u m 2 + 2 × v a l × s u m 1 + l e n × v a l 2 sum_3 = sum_3 + sum_2 + 2 \times val \times sum_1 + len \times val^2 sum3​=sum3​+sum2​+2×val×sum1​+len×val2

把上面的式子整理一下，就可以用矩阵乘法维护，转移矩阵： [ 1 v a l v a l 2 v a l 2 0 1 2 × v a l 2 × v a l 0 0 1 1 0 0 0 1 ] \begin{bmatrix} 1& val& val^2& val^2\\ 0& 1& 2\times val& 2 \times val\\ 0& 0& 1& 1\\ 0& 0& 0& 1 \end{bmatrix} ⎣ ⎡​1000​val100​val22×val10​val22×val11​⎦ ⎤​ 看了看题解，说“设置了一个让不需要任何矩乘优化就可勉强通过的时限”，说明有卡常？

但并没有卡到（

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10, MOD = 1e9 + 7;
int a[N], ans[N];

namespace ffastIO {
	const int bufl = 1