GSS - Can you answer these queries

GSS - Can you answer these queries 系列做题记录！

GSS1 SP1043 IN Lv.13

这道题的关键其实就是区间合并。

定义区间结构体（这里命名为 QJ），内部存储从左端点开始的最大值、和从右端点开始的最大值、区间和和区间答案。

合并的时候分类讨论取即可。

GSS2 SP1557 IN Lv.15

这道题和 GSS1 的区别就是加了一个“相同的数只算 1 次”。但是加了这个限制之后，就没有办法用上一道题的方法去做。只能换一个方法。

因为这道题涉及相同的数只算次，之前遇到过的类似的题目“HH的项链”的做法是将询问离线，然后实时更新，将其搬到树状数组上做。所以这道题也可以将询问离线，实时更新。但是因为这道题求的是，无法树状数组区间求，只能搬到线段树上。

还是，首先将询问区间按照右端点排序。然后修改就从左到右改。设表示子段的子段和，这里定义线段树节点为，线段树维护最大值。那么每次新遍历到一个点，那么就在线段树上让区间全部加上。然后查询所有的即可。

但是遇到了一个问题：最优的子段并不总是以结尾。为了处理这个问题，我们要在线段树节点上记录历史最大值和历史最大 lazytag。某一个节点的历史最大值就是。

具体的，每一个线段树节点维护 4 个变量：

maxi, lazy：普通的区间最大值和 lazytag。
maxiold：历史区间最大值。
lazyold：历史 lazytag 最大值。

于是查询的时候查询 maxiold 变量在的最大值即可。

因此，还需添加一个 modify_old(int x, int w) 操作，表示将的历史最大值加上。加的时候应遵循如下规则：

void modifyold(int x, int w){
    tr[x].maxiold = max(tr[x].maxiold, tr[x].maxi + w);
    tr[x].lazyold = max(tr[x].lazyold, tr[x].lazy + w);
}

然后 pushdown 操作也应修改。先做 pushdown lazyold 操作，然后再执行 pushdown lazy 操作。于是这道题就做完了。

GSS3 SP1716 IN Lv.13

这道题定数比 GSS1 还要低，似乎会了 GSS1 就会 GSS3 了。

还真是。就是 GSS1 加个修改操作而已。

GSS4 SP2713 IN Lv.14

这道题比较有意思。但是这道题的输入和输出格式非常恶心，请注意。

第一眼发现是区间开方，但是区间开方是不能用区间或是区间实现的。非常恶心。

但是如果你闲得慌，在计算器上按一按：

1
2
3

> calc
> sqrt(sqrt(sqrt(sqrt(sqrt(sqrt(1,000,000,000,000,000,000))))))
1.91095297497044...

那么这道题不就炸了吗。就算是的值域，只要开方最多 6 次，都会变成 1。

于是就可以愉快地写线段树：维护区间的和区间的。变量表示这段区间的权值是否全部。如果是，那么你再开方也白干。修改就直接暴力修改，修改的同时维护。反正也最多修改次，就算带个甚至也不会超时。

GSS5 SP2916 IN Lv.15

这道题其实就是标准的查询区间子段和和一些分讨。

若，即两个区间没有交。那么答案就是。
否则，两个区间有交。于是现在大小关系就变为。讨论两个端点在哪个区间的情况。设：
- 左端点在，右端点在，答案为。
- 左端点在，右端点在，答案为。
- 左端点和右端点均在，答案为。

GSS6 SP4487 IN Lv.15

这道题让~~好不容易~~忘了平衡树的我重新打开了 FHQ 平衡树博客。

注意：这道题描述的“在处插入一个元素”是指在和中插入。

这道题因为要实现单点插入、单点修改、单点删除和区间查询，所以可以想到用平衡树来做这道题。因为平衡树可以高效查找，并且可以维护区间。

我们定义每一个平衡树节点，除了需要维护平衡树基本的 ls, rs, pri, val, siz，因为要维护区间最大子段和，所以还要加上 lftans, rgtans, sum, ans。

因为每一个 pushup 是要涉及到 3 个节点：。所以要把维护区间最大子段和稍微修改修改。我们可以在最开始 newnode(int w) 的时候，lftans 和 rgtans 取。因为有可能是负数。而 ans 则要取，因为它的子段大小不能等于。

然后 pushup 的时候还是正常 pushup：

void pushup(int x){
    tr[x].siz = tr[tr[x].ls].siz + tr[tr[x].rs].siz + 1;
    tr[x].lftans = max(tr[ls(x)].lftans, tr[ls(x)].sum + tr[x].val + tr[rs(x)].lftans);
    tr[x].rgtans = max(tr[rs(x)].rgtans, tr[rs(x)].sum + tr[x].val + tr[ls(x)].rgtans);
    tr[x].sum = tr[ls(x)].sum + tr[x].val + tr[rs(x)].sum;
    tr[x].ans = max({tr[ls(x)].ans, tr[rs(x)].ans, tr[ls(x)].rgtans + tr[x].val + tr[rs(x)].lftans});
}

然后因为是根据位置插入、删除或修改，所以分裂的时候只能按 siz 来分裂。接下来详细说明操作步骤：

I p x：分裂前和后面的，然后中间插入，最后合并。
D p：分裂前和后面的，为两棵树。再把第一棵树分裂前和后，也为两棵树。最后合并前和后面的那棵。
R p x：像操作 2 一样分裂。分裂后按照 newnode 步骤修改中间的的树。最后依次合并。
Q l r：依次分裂出三棵。最后直接输出中间那棵的 ans，最后依次合并即可。

GSS7 SP6779 IN Lv.16

见树链剖分专题内链接。（话说这道题还是我做的第一道 GSS）

这道题还是典型的区间合并 + 树链剖分问题。但是这里有一个小细节：

因为每一个点的权值可以为负，所以在设 Lazytag 的时候一定要把初始值设为极大值或是极小值。要不然你会死掉。

GSS8 SP19543 IN Lv.16

注意：这道题下标从开始。

这道题和 GSS6 非常像。但是它要询问一个非常抽象的玩意。

因为，所以我们可以在每一个平衡树节点中，开一个大小为的数组，存储对于每一个的答案，记为。对于平衡树节点，它对应的序列就是。由于查询的这个式子非常抽象，所以我们转化一下式子。

$\begin{aligned} ans_{x, k} &= \sum_{i=l}^{r} a_i (i-l+1)^k \\ &= \sum_{i=l}^{mid} a_i(i-l+1)^{k} + \sum_{i=mid+1}^{r} a_i(i-l+1)^k \\ &= ans_{ls,k} + val_{mid} \times (mid-l+1)^{k} + \sum_{i=mid+1}^{r} a_i[(mid-l+1)+(i-mid)]^k \end{aligned}$

因为是一个定值，所以可以先求出这个。然后后面的式子，根据二项式定理，可得：

$\begin{aligned} \sum_{i=mid+1}^{r} a_i[(mid-l+1)+(i-mid)]^k &= \sum_{i=mid+1}^{r} a_i \sum_{j=0}^{k}C_{k}^{j}(mid-l+1)^{k-j}(i-mid)^{j}\\ &= \sum_{j=0}^{k}C_{k}^{j}(mid-l+1)^{k-j}\sum_{i=mid+1}^{r} a_i(i-(mid+1)+1)^{j}\\ &= \sum_{j=0}^{k}C_{k}^{j}(mid-k+1)^{k-j}ans_{rs,j} \end{aligned}$

于是就可以根据这个式子，实现 pushup 过程。的幂次可以预处理。组合数也可以实现预处理。由于，所以基本没有啥影响。

然后剩下的就和 GSS6 差不多了。

后记

终于做完了。8 道题硬控了我 2 天。

据说以前，GSS 的每一道题难度都是现在难度上一级，5 道黑。只不过现在黑降紫，紫降蓝了。

不过当我开始做 GSS7，手搓出来 IN Lv.16，心里是非常激动的，毕竟还是第一次手搓出来一道这样的题。

8 道题做完了，对于线段树维护区间子段和的旅程就先告一段落了。

目前个人难度排行：。

希望等 GSS9 正式上线洛谷的时候，也能将其做出来！ο(=•ω＜=)ρ⌒☆