2019~2020学年度上OI总结

既然搬运了$GSS$的题目，那当然还是要写一下题解的啦(树剖部分最好会搬运过来，最坏可能并不会搬运)

---

$$GSS1$$

题目传送门: $OJ $$luogu$

题意:给出了序列以及$m$组询问，求每组询问区间内的最大子段和.

首先，$GSS$全是数据结构题，因此我们不会去用之前$O(n)$的方法查询，因为这样在最坏情况下时间会退化为$O(nm)$

否决了$O(nm)$的做法之后，再考虑数据结构的话，线段树就是一个不错的选择了.

但是这颗线段树需要维护些什么呢，我们来具体分析一下。

目标是最大子段和，我们以根节点与左右子节点的$push_up$关系来加以阐明,查询也就没什么区别了

对于一个大区间的最大子段和(记为$dat$),它无非有三种情况:

1. 它就是左区间的最大子段和(一定在左区间)
2. 它就是右区间的最大子段和(一定在右区间)
3. 它横跨左右两个区间

这三种情况取最大值即可。对于前两种情况,我们很好维护，但第三种呢?
举个例子:

2 -4 3 1    -2 4 3 1

这个区间的最大子段和是$[3,8]$,对于横跨两边的最大子段和，毋庸置疑的是它一定包括:左区间的右端点和右区间的左端点。此后的一切都是它根据这个延伸出来的。比如在上面的例子中，我们将左区间的$1$再扩展到$3 1$,将右区间的$-2$扩展到$-2 4 3 1$

再继续观察，我们可以发现:

• 对于左区间,它的延伸区间一定是以右端点为终止点的最大子段和.($lmaxn$)
• 对于右区间,它的延伸区间一定是以左端点为起始点的最大子段和.($rmaxn$)

所以我们的线段树再维护一个$lmaxn$和$rmaxn$,那我们又怎么求出每个区间的$lmaxn$和$rmaxn$呢.还是举两个例子

2 4 -3 5  2 -3 1 2

对于这一个区间,它的$lmaxn$是$[1,5]$

2 4 -9 5 2 -3 1 2

对于这一个区间,它的$lmaxn$是$[1,2]$

多举几个例子，很容易看出:

• $lmaxn$要么就是左区间的$lmaxn$,要么就是整个左区间加上右区间的$lmaxn$
• $rmaxn$要么就是右区间的$rmaxn$,要么就是整个右区间加上左区间的$rmaxn$
  至于这个结论为什么成立，读者自证.

到这里，我们就能够明确地看到，这个线段树要维护$4$个信息:$dat,lmaxn,rmaxn,sum$ ，更新方式为:

$$\texttt{tr[p].dat=max\{tr[p<<1].dat,tr[p<<1|1].dat,tr[p<<1].rmaxn+tr[p<<1|1].lmaxn\}}$$ $$\texttt{tr[p].lmaxn=max\{tr[p<<1].lmaxn,tr[p<<1].sum+tr[p<<1|1].lmaxn\}}$$ $$\texttt{tr[p].rmaxn=max\{tr[p<<1|1].rmaxn,tr[p<<1|1].sum+tr[p<<1].rmaxn\}}$$ $$\texttt{tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum}$$

查询时也以此类推，即可求出最大子段和。

$\mathcal{CODE}$

---

$$GSS2$$

题目传送门: $OJ $$luogu$

$$\texttt{太弱了，做不出来}$$

---

$$GSS3$$

题目传送门: $OJ $$luogu$

这道题跟$GSS1$有区别吗?双倍经验好吗?

$\mathcal{CODE:}$不展示

---

$$GSS4$$

题目传送门: $OJ $$luogu$

第一眼我们还是会去想能不能像加法的线段树一样，打$lazy tag$,但很快我们就会否决掉，原因很简单:

$$\sqrt{a+b}≠\sqrt{a}+\sqrt{b}$$

那我们能不能把区间拆成单点修改呢?可能不能···吧?

再从数据范围下手:

保证$\sum a \le 10^{18}$

好的，我们掏出计算器来看一看(均向下取整):

$$\sqrt{10^{18}}=10^9\ \ \sqrt{10^9}=31622\ \ \ \sqrt{31622}=177\ \ \ \sqrt{177}=13\ \ \ \sqrt{13}=3 \ \ \ \sqrt{3}=1···$$

只需要$6$次，我们的$10^{18}$就可以被开到$1$,换句话说对每一个数的开方次数不会超过$6$次.

现在，我们再拿这颗线段树顺便维护一下区间最大值，若区间最大值大于$1$,那么我们就不用修改了.

(最大)时间复杂度:$O(6*(n+m)logn)$

$\mathcal{CODE}$

---

$$GSS5$$

题目传送门:$OJ $$Luogu$

温馨提醒:请确保您已看懂$GSS1$的题解，这篇题解将围绕它展开.

对于这道题，做完过后觉得它其实只有紫题水平吧 ,但为什么做之前觉得它是纯种黑题呢?

我们来复习一下对于最大子段和,($GSS1$)我们维护了哪些信息?

区间最大前缀和$(lmaxn) $ 区间最大后缀和$(rmaxn) $区间和$(sum) $ 区间最大子段和$(dat)$

现在,我们看这道题,它的两个区间有下面三种情况(借用了圆的思想):
1.相离($l_2r_1$)

$1.$两个区间相离

如图，答案即为

$$\texttt{rmaxn[l1,l2)+sum[l2,r1]+lmaxn(r1,r2]}$$

$2.$两个区间相切

如图，答案即为

$$\texttt{rmaxn[l1,l2)+lmaxn[r1,r2]}$$

$3.$两个区间相交

这其中又有四种情况.这里不一一画图，大家可以自己理解一下.(说白了就是懒得画)
$(1).$答案的区间两个端点在$[l2,r1]$

$$\texttt{dat[l2,r1]}$$

$(2).$答案的区间起点在$[l1,l2]$,终点在$(l2,r1]$

$$\texttt{rmaxn[l1,l2]+lmaxn(l2,r1]}$$

$(3).$答案的区间起点在$[l2,r1]$,终点在$(r1,r2]$

$$\texttt{rmaxn[l2,r1]+lmaxn(r1,r2]}$$

$(4).$答案的区间起点在$[l1,l2]$,终点在$[r1,r2]$

$$\texttt{rmaxn[l1,l2)+sum[l2,r1]+lmaxn(r1,r2]}$$

在上面四种情况中去取最大值即可

但实现的时候可能会有一点问题，为什么呢?我们的线段树存储的是闭区间的信息，但这里会有半开半闭的情况.
但是你们这么聪明,肯定知道怎么办,就不用我多嘴了(雾

$\mathcal{CODE}$:不提供，情况都列出来了应该把$1$的代码稍稍改一下即可.

---

在更完之前，这张自拍都会贴在这里.

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1275881998@qq.com