GSS 是啥意思？
好像是最大子段和的意思？
是 SPOJ 里面的一组 DS 题哦！标题都是「Can you answer these queries」，以这些题为例子，向大家介绍一些基础的 DS 套路。
笔者水平有限，若文章中有些许错误或者不当之处还请多多指正。
（GSS 题目的顺序和难度顺序十分不一致，这里按照题目顺序排序）
GSS1 - Can you answer these queries I
给定长度为 n 的序列 A，q 次询问求区间最大子段和。n,q \leq 5 \times 10^4。
最大子段和了即为是选一段连续的子段使得其和最大，也就是 \max_{1\leq l\leq r\leq n}\{\sum_{i=l}^ra_i\}。
为了方便我们记最大子段为和为 \sigma。
首先考虑暴力的方法？每次在区间里 DP 一下，\sigma_i=\max\{\sigma_{i-1}+a_i,a_i\}。
时间复杂度的话是 O(nq) 这样。
不过注意到解最大子段和有一个分治解法。
考虑在分治到一个区间合并时，左右子区间的答案已经计算完毕，剩下一种就是左端点在左区间，右端点在右区间的情况。由选段是连续的，这时只需要计算左区间的最大后缀，右区间的最大前缀，其和就是答案。然后这三种情况取 \max 就好。
时间复杂度？每次暴力算最后一种情况需要 O(n) 的代价，那么递归式就是 T(n)=2T(
\frac{n}{2})+O(n)=O(n\log n)，总复杂度 O(qn\log n)。
欸？又还多了一个 \log 欸，更慢了呢。
不过这可以带给我们一个启发：最大子段和这个信息是满足结合律，并且可以快速合并的，实际上最大前后缀也是这样。
而线段树是天然的分治结构，我们自然地想到用它来维护这些信息。
我们在线段树节点中维护 \sigma，考虑某个节点 u 的 pushup 操作
，由于它左右儿子 v,w 已经维护好 \sigma，还剩下一个没有被计算的情况就是左端点在左儿子的区间，右端点在右儿子的区间的这样一个子段。
一样地，我们再在每个节点维护一个最大前缀 \psi_{u,0} 和最大后缀 \psi_{u,1}，合并的代价是 O(1) 的，\sigma_u\rightarrow\max\{\sigma_v,\sigma_w,\psi_{v,1}+\psi_{w,0}\}。
接下来考虑如何维护 \psi，一样分情况讨论，其合并时只有两种情况：是否跨过左右区间的中点。
用前缀 \psi_{u,0} 举个例子，若不跨过中点，那么 \psi_{u,0}\rightarrow\psi_{v,0}，否则我们需要再维护一个区间和 \Sigma_u，\psi_{u,0}\rightarrow\Sigma_v+\psi_{w,0}。两种情况取 \max。
后缀也是同理维护。
那么时间复杂度就是 O(n+q\log n) 的了，十分的优秀！
现在我们对一开始暴力 DP 的方法进行一些修缮。
以 i 为结尾的最大子段和 \sigma_i=\max\{\sigma_{i-1}+a_i,a_i\}，当前答案 f_i=\max\{f_{i-1},\sigma_i\}=\max\{f_{i-1},\sigma_{i-1}+a_i,a_i\}。初值 \sigma_0=-\infty,\ f_0=0。
我们用两个运算 \otimes,\oplus 代替乘法和加法，定义广义矩阵乘法 A\times B=C，C_{i,j}=\bigoplus_{k=1}^nA_{i,k}\otimes B_{k,j}。
然后令 \oplus=\max,\otimes=+，考虑把 i-1\rightarrow i 的转移 写成广义矩阵乘法的形式：
\sigma_{i-1}&f_{i-1}&0
\end{bmatrix}\times M_i=\begin{bmatrix}
\sigma_{i}&f_{i}&0
\end{bmatrix}
其中 M_i 就是我们需要对每个 i 构造的转移矩阵。
我们知道矩阵乘法是有结合律的，那么我们创造的广义矩阵乘法若它的运算分别也都有结合律，广义矩阵乘法应当也是有结合律的。（ 实际上确实有 ）由此，我们从 i 一直 DP 到 j 的操作就可以转化为初始矩阵乘上 M_i,M_{i+1},\cdots,M_{j} 的连乘积。
一通手算后可以构造出 M_i：
a_i&a_i&-\infty\\
-\infty&0&-\infty\\
a_i&a_i&0\\
\end{bmatrix}
初始矩阵为：
\begin{bmatrix}\sigma_0&f_0&0\end{bmatrix}=\begin{bmatrix}-\infty&0&0\end{bmatrix}
（ 具体该如何构造的话只需记住答案矩阵第 n 行第 m 列是 A 的第 n 行与 B 的第 m 列从头开始对应加后取 \max 的结果，然后凑数。）
那么问题转化为取出一段区间的矩阵连乘积再乘上初始矩阵，所以可以直接在线段树上维护矩阵乘法就好了。
时间复杂度 O(k^3q\log n)，O(k^3) 是做矩阵乘法的开销。
可以发现这样做也是支持单点修改的，这样把 DP 写成矩阵乘法的形式后在数据结构上动态维护的做法称为 " 动态 DP "。
GSS2 - Can you answer these queries II
首先引入最大子段和的另一种做法。
考虑以区间左端点为纵轴，右端点为横轴，一条垂直于横轴的线从左往右做扫描线，设一个点 (r,l) 的权值为 \Sigma_{l,r}，那么我们的一个询问 (L,R) 实际上是查一个三角形中的最大点权，即 \max_{L\leq l\leq r\leq R}\{\Sigma_{l,r}\}。
其实由于 l\leq r 的限制，l=r 这条直线上方的点权皆为 0，所以也可以看做对 l=r 这条直线下的一个三角形的查询，我们延申这个三角形的两条直角边，这就是一个 \text{2-side} 矩形。
那么扫描线扫 r 维，数据结构维护 l 维，当扫描线 r\rightarrow r+1 时我们该如何维护信息？
注意到我们询问的是一个 \text{2-side} 矩形，这是非常好的，因为这意味着我们每次询问的是一个前缀矩形，我们无须对这个矩形中点的横坐标做任何限制，故我们可以把维护 l 维的数据结构在 r 维上压缩，只需在扫描线扫到 r 时维护一个数组 B，满足 b_i=\max_{1\leq x\leq r}\{\Sigma_{i,x}\}，然后在 B 上做区间最值查询。
维护 B，扫描线 r\rightarrow r+1 时要加入 a_{r+1} 的贡献。
我们再维护一个 C，满足 c_i=\Sigma_{i,r}，维护 C 是很容易的，只需在 r\rightarrow r+1 时将 c_{1} 至 c_{r+1} 区间加 a_r+1 即可。
接着我们发现当扫到 r 时，c_i 的值已经取遍了 \Sigma_{i,x}(1\leq x\leq r)，它的历史最大值即为 b_i！这样我们就完成了所有的工作。
如此下来我们离线询问，需要支持 O(n) 次区间加，O(q) 次区间历史 \max，用吉司机线段树即可做到 O((n+q)\log n)。
好的，让我们回到原题，为什么要先引入这个似乎麻烦很多的做法呢？
大概是因为原来直接线段树维护序列的方式难以快速维护 "只计算一次" 的信息，而放到扫描线上就非常好做了，设 a_i 上一次出现的位置为 \operatorname{pre}_i，在加入 a_{r+1} 贡献时我们只加到 [\operatorname{pre}_{r}+1,r+1] 这个区间里即可，可以发现这样两个重复元素不会被贡献到同一个区间内，我们的点权就都是正确的了。
P1972 [SDOI2009] HH的项链
有很多做法，我们尝试用上面的扫描线模型来解决它。
首先是以左端点为纵轴，右端点为横轴做扫描线，我们直接设一个点 (r,l) 的点权为区间 [l,r] 的答案，扫描线扫横轴，数据结构维护纵轴，询问转化为求点权。
当扫描线 r\rightarrow r+1 时加入 a_{r+1} 的贡献，设 a_i 上一次出现的位置为 \operatorname{pre}_i，实际上它对所有 [i,r+1],\ (\operatorname{pre}_{r+1}+1\leq i\leq r+1) 的询问都有 1 的贡献，因为这个区间中 a_{r+1} 第一次出现，所以在纵轴上做一个区间加即可。
另一个做法是把所有元素 a_i 变为一个二维的点 (\operatorname{pre}_i,i)，那么我们一个询问 [l,r] 实际上是询问所有的满足第一维在 [l,r] 之外，第二维在 [l,r] 之内的点的数量，我们称这种问题为 ”二维数点“ 即给出平面上若干个点，每次询问一个矩形中点的数量。
这里的二维数点是静态的，我们把询问矩形拆成两个前缀矩形的差分：
变为下图两个矩形的答案差：
所以直接扫描线扫过去，线段树维护纵轴，遇到点在线段树上单点加，由于我们询问的都是前缀矩形所以我们无需关心横轴上的限制，在线段树上区间求和即可。
时间复杂度均为 O((n+q)\log n)。
GSS3 - Can you answer these queries III
GSS3 区别于 GSS1 就是带单点修改，由于分治信息的原因，我们就只需要下到叶子节点修改再合并上去即可。
那么区间覆盖该怎么做呢？
一般线段树需要通过打懒标记来实现这些事情，因为我们不能全部递归到叶子，将修改区间在线段树上拆分成若干个被完全包含的最浅的区间，这样的区间数量是 O(\log n) 的，我们只修改这些点并打上标记，等到需要更深层的信息时我们再将它们下传。
那么这样的懒标记需要满足一些条件，比如可以根据当前节点的答案快速计算出修改后的答案而不需要更深层的信息，以及可以快速合并，并在时间轴上具有结合律，可以不具有交换律，因为一定是一个较晚的标记和当前标记合并。
那么对于这个操作我们设置一个标记 x 表示修改的数，当一个节点 u=[l,r] 被打标记时可以直接 O(1) 计算出答案的变化。\Sigma_u\rightarrow(r-l+1)\times x，考虑到必须选一个的限制，如果 x>0 那么全选，\ \psi_{u,0}=\psi_{u,1}=\sigma_u\rightarrow(r-l+1)\times x，否则只选一个 \ \psi_{u,0}=\psi_{u,1}=\sigma_u\rightarrow x。
接下来考虑合并标记，设 x_1 合并到 x_0 为 x_0\oplus x_1 上那么显然 x_0\oplus x_1=x_1。
时间复杂度 O(n+q\log n)。
练习 1：给区间乘区间加区间求和打标记。
取这样一个标记 (x,y) 表示先乘 x 再加 y，这样不会造成顺序的歧义，那么当一个节点 u=[l,r] 被打标记时 \Sigma_u\rightarrow \Sigma_u\times x+y。
接下来考虑合并，根据乘法分配律直接得到 (x_0,y_0)\oplus (x_1,y_1)=(x_0\times x_1,y_0\times x_1+y_1)。
容易发现它也具有结合律。
练习 2：给 GSS3 中的区间加区间历史 \max 打标记。
区间和历史 \max 指查询一个区间中的所有元素曾达到过的最大值。
用 m 表示当前最大元素，h 表示历史最大元素。
思索一下，由于修改是区间加，那么该区间所有元素整体加 k 后的最大元素应该是 m+k，设 k 在这些加减操作中所达到过的最大值为 k_{\max}，这个区间的历史最大值 h 就应当是 z+k_{\max}。
取这样一个标记 (x,y) 表示整体加 x，这个标记的 x 曾达到过的最大值为 y，那么当一个节点 u 被打标记时 h_u\rightarrow \max(h_u,m_u+y),\ m_u\rightarrow\max(m_u,m_u+x)。注意这两个更新是有顺序的。
接下来考虑合并，由于时间轴上有序，仿照上面的意义有 (x_0,y_0)\oplus(x_1,y_1)=(x_0+x_1,\max(y_0,x_0+y_1))。
容易发现它也具有结合律。
最后我们考虑如何用 GSS1 中数据结构维护矩阵的方式来做。
单点修改是容易的，区间覆盖时我们要快速计算新答案。
当区间 [l,r] 中所有数都变成 x 时，区间答案自然变为 M^{r-l+1}=\begin{bmatrix}
x&x&-\infty\\
-\infty&0&-\infty\\
x&x&0\\
\end{bmatrix}^{r-l+1}，矩阵快速幂即可。
GSS4 - Can you answer these queries IV
这题不是最大子段和，而是区间开方和区间求和。
首先，维护区间和所含的信息对于区间开方是不够的，这意味着如果你要对一个数开方，必须要修改对应的叶节点再 pushup 上去而无法通过打懒标记来降低复杂度。
如果这样做的话一次会修改 O(n) 个叶节点，总时间复杂度 O(qn)。
开方有什么性质可以利用呢？我们发现 \sqrt{1}=1,\sqrt{0}=0，而一个数 V 在开 O(\log\log V) 次方下取整后总会变为 1。
那么也就是说，假若某个数为 1 或 0，我们就可以不对其进行操作。
于是我们可以维护一个区间 \max，假若一个区间的 \max 为 1 或 0，在线段树修改的时候可以不进入它。
分析一下复杂度？如果某个叶节点被访问到，对应的数会被开一次根。而值为 1 的叶子不会被再次访问，访问一次叶子对应 O(\log n) 的复杂度，n 个叶子总共被访问 O(n\log\log V) 次。于是总复杂度就是 O(n\log n\log\log V)。
还有一种做法是树状数组加并查集，我们在序列下标上建立并查集，初始每个元素都是独立的。
假若有两个相邻的元素是 0 或经过 O(\log\log V) 次开方后变为 1，我们就将其合并，修改时可以利用并查集来跳过一段元素都为为 0 或 1 的区间。
GSS5 - Can you answer these queries V
本题查询的是左端点在 [l_1,r_1]，右端点在 [l_2,r_2] 之间的最大子段和。
首先我们仍然可以和 GSS1 一样维护一下线段树的信息。
本题没有保证两个端点区间不相交，但是我们可以先着手看一下两区间不相交的情况。
那么这个最大子段和一定会覆盖两端点区间中间空出的那一段，设左端点区间为 l，右端点区间为 r，中间的区间为 m，那么最大子段和就是 \psi_{l,1}+\Sigma_m+\psi_{r,0}。
那么假若两区间相交，设相交的区间为 m，[l_1,r_1] - m 这一区间为 l，[l_2,r_2] - m 为 r。
现在左端点可以在 l , m 这两个区间移动，右端点可以在 m,r 这两个区间移动。这样就可以分情况讨论了。
当左端点在 l，右端点在 r 时，最大子段和为 \psi_{l,1}+\Sigma_m+\psi_{r,0}。
当左端点在 l，右端点在 m 时，最大子段和为 \psi_{l,1}+\psi_{m,0}。
当左端点在 m，右端点在 r 时，最大子段和为 \psi_{m,1}+\psi_{r,0}。
当左右端点都在 m 时，最大子段和为 \sigma_m。
四种情况取 \max 就是答案。
时间复杂度 O(n+q\log n)。
GSS6 - Can you answer these queries VI
比起 GSS3，GSS6 支持序列上的插入与删除，用平衡树维护。
平衡树维护序列的原理是以元素下标为键值建立平衡树，所以序列的第 i 个元素变为树中 \operatorname{rank}=i 的节点，在树中一个节点维护它的子树信息合并，如果我们需要一个区间 [l,r] 的信息就可以利用平衡树分裂出 l\leq \operatorname{rank}\leq r 的这颗子树，查询根的信息即可。
比如 \text{Splay} 中我们把 \operatorname{rank}=l-1 的点 l' 伸展到根，再把 \operatorname{rank}=r 的点 r' 伸展到根的右子树，根据平衡树节点的规则此时 r' 的左子树中的点的 \operatorname{rank} 都在 [l,r] 之间了。
这样维护的好处是我们支持在序列中插入或删除数了，不过这样会导致后面的数的权值变化，我们就直接舍弃以权值来定义 \operatorname{rank} 而是用子树大小查第 k 大的结果来定义 \operatorname{rank}，这样插入删除就可以直接做了，只需要维护每个点的 \operatorname{size}。
打标记等操作沿用线段树的做法。
时间复杂度 O(n+q\log n)。
GSS7 - Can you answer these queries VII
GSS7 是把整个问题放到了树上，并且是链上区间覆盖的修改，链上查最大子段和，可以不选。
首先看到链查链改先打个树剖出来，再考虑如何维护。
在区间覆盖的操作下维护那四个值不难，如果一个长度为 z 的节点被覆盖为 x 那么 \Sigma\rightarrow z\times x,\sigma=\psi_0=\psi_1\rightarrow \max\{0,z\times x\}。
为什么？因为可以不选，若 x 非负一定全选，否则一个位置都不选。
不过最大子段和没有交换律，合并时要求两边的信息顺序是对的，在一条链上向上跳询问出的前缀是向着祖先的，所以合并时要把需要合并到答案的信息放到左边。
在两点都跳到同一条重链上时两边的前缀都是向着祖先的，所以需要翻转一边的前后缀后再合并。
时间复杂度 O(n+q\log^2 n)。
GSS8 - Can you answer these queries VIII
这题要求插入与单点改，以及区间查询：
\sum_{i=l}^ra_i\times(i-l+1)^k
其中 k 是给定的，且 0\leq k\leq 10。
设这一式子为 f^k，想想怎么合并答案。
设左区间 [l,m]，右区间 [m+1,r]。为了合并，我们尝试表示出两个子区间的答案。
f^k_u=&\sum_{i=l}^ra_i(i-l+1)^k\\
=&\sum_{i=l}^ma_i(i-l+1)^k+\sum_{i=m+1}^ra_i(i-l+1)^k\\
=&f^k_v+\sum_{i=m+1}^ra_i(i-(m+1)+1+(m-l+1))^k\\
=&f^k_v+\sum_{i=m+1}^ra_i\sum_{j=0}^k\binom{k}{j}(i-(m+1)+1)^j(m-l+1)^{k-j}\\
=&f^k_v+\sum_{j=0}^k\binom{k}{j}(m-l+1)^{k-j}\sum_{i=m+1}^ra_i(i-(m+1)+1)^j\\
=&f^k_v+\sum_{j=0}^k\binom{k}{j}(m-l+1)^{k-j}f_w^j\\
\end{aligned}
预处理出组合数就可以 O(k^2) 合并所有 k 的答案了。
放到平衡树上做，时间复杂度 O(k^2q\log n)。
upd : 2022.9.23
时隔七个月发现这个东西过日报了，于是来对整篇文本修缮了一下。
这一组题可以说是笔者的 DS 启蒙题，涉及的元素大概有
希望大家有所收获！