GSS 是啥意思？
好像是最大子段和的意思？
是 SPOJ 里面的一组 DS 题哦！标题都是「Can you answer these queries」，涵盖了很多基础的 DS 技巧，可以做一下。
好不容易把全部的题码完了，突然发现网上好像少有这一套题的整合题解 ... 于是来写一发题解~
笔者水平有限，若文章中有些许错误或者不当之处还请多多改正。
GSS1 - Can you answer these queries I
给定长度为 \(n\) 的序列 \(A\)，\(q\) 次询问求区间最大子段和。数据范围的话，\(n,q \leq 5 \times 10^4\)。
最大子段和了即为是选一段连续的子段使得其和最大，也就是 \(\max_{1\leq i\leq j\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=\max\{\sigma_v,\sigma_w,\psi_{v,1}+\psi_{w,0}\}\)。
接下来考虑如何维护 \(\psi\)，一样分情况讨论，其合并时只有两种情况：是否跨过左右区间的中点。
用前缀 \(\psi_{u,0}\) 举个例子，若不跨过中点，那么 \(\psi_{u,0}=\psi_{v,0}\)，否则我们需要再维护一个区间和 \(\Sigma_u\)，\(\psi_{u,0}=\Sigma_v+\psi_{w,0}\)。两种情况取 \(\max\)。
后缀也是同理维护。
那么时间复杂度就是 \(O(q\log n)\) 的了，十分的优秀！
GSS2 - Can you answer these queries II
首先引入最大子段和的另一种做法。
考虑以区间左端点为纵轴，右端点为横轴做扫描线，设一个点 \((r,l)\) 的权值为 \(\Sigma_{l,r}\)，那么我们的一个询问 \((L,R)\) 实际上是查一个矩形中的最大点权（其实由于 \(l\leq r\) 的限制，\(l=r\) 这条直线上方的点权皆为 \(0\)，所以也可以看做对 \(l=r\) 这条直线下的一个三角形的查询，我们延申这个三角形的两条直角边，这就是一个 \(\text{2-side}\) 矩形），即 \(\max_{l,r\in[L,R]}\{\Sigma_{l,r}\}\)。
那么扫描线扫 \(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]\) 这个区间里即可，可以发现这样两个重复元素不会被贡献到同一个区间内，我们的点权就都是正确的了。
GSS3 - Can you answer these queries III
GSS3 区别于 GSS1 就是带单点修改，可以发现这玩意还是非常容易维护，直接把对应叶节点的 \(\sigma,\psi,\Sigma\) 全部修改成那个值即可。pushup 会帮助你解决剩下所有的问题。
时间复杂度 \(O(q\log n)\)。
GSS4 - Can you answer these queries IV
这题不是最大子段和，而是区间开方和区间求和。
首先，维护区间和所含的信息对于区间开方是不够的，这意味着如果你要对一个数开方，必须要修改对应的叶节点再 pushup 上去而无法通过打懒标记来降低复杂度。
如果这样做的话一次会修改 \(O(n)\) 个叶节点，总时间复杂度 \(O(qn\log n)\)，甚至不如暴力。
开方有什么性质可以利用呢？我们发现 \(\sqrt{1}=1,\sqrt{0}=0\)，而一个数 \(V\) 在开 \(O(\log\log V)\) 次方下取整后总会变为 \(1\)。
也就是说，假若某个数为 \(1\) 或 \(0\)，我们就可以不对其进行操作。
于是我们可以维护一个区间最大值，假若一个区间的最大值为 \(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(q\log n)\)。
附图如下。
GSS6 - Can you answer these queries VI
比起 GSS3，GSS6 支持序列上的插入与删除，这个就是个平衡树维护序列的板子了。
和线段树一样，我们维护 \(\psi_0,\psi_1,\sigma,\Sigma\) 这四个值，不过要注意平衡树并非 Leafy，在合并左右儿子的答案时要注意加上其自身的值。
时间复杂度 \(O(q\log n)\)。
GSS7 - Can you answer these queries VII
GSS7 是把整个问题放到了树上，并且是链上区间覆盖的修改，链上查最大子段和，可以不选。
首先看到链查链改先打个树剖出来，再考虑如何维护。
在区间覆盖的操作下维护那四个值不难，如果一个长度为 \(z\) 的节点被覆盖为 \(x\) 那么 \(\Sigma\rightarrow z\times x,\sigma\rightarrow \max\{0,z\times x\},\psi_0=\max\{0,z\times x\},\psi_1=\max\{0,z\times x\}\)。
为什么？因为可以不选，若 \(x\) 非负一定全选，否则一个位置都不选。
不过最大子段和的合并要求两边的信息顺序是对的，在一条链上向上跳询问出的前缀是向着祖先的，所以合并时要把需要合并到答案的信息放到左边。
在两点都跳到同一条重链上时两边的前缀都是向着祖先的，所以需要翻转一边的前后缀后再合并。
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]\)。
\[\begin{aligned} 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 启蒙题，涉及的元素大概有
-
可以快速合并的信息
-
扫描线模型
-
在值域上考虑
-
把问题移植到树上 / 平衡树上的问题
-
简单的推式子
希望大家有所收获！
标签：GSS,psi,log,子段,复杂度,SPOJ,端点,区间,DS From： https://www.cnblogs.com/yukari1735/p/16724648.html