如何速通GSS的水题

Tiffake · 2024-12-09 22:03:35 · 个人记录

如何速通GSS的水题

GSS1 - Can you answer these queries I

思路

看到区间查询，线段树启动。
考虑如何维护最大子段和，发现其本质是求区间中某一段的和。这一段和该如何转移？

考虑最简单的情况，n=1，答案无疑是它本身。
考虑两块区间如何合并：

1. 来自左区间的答案。
2. 来自右区间的答案。
3. 来自左区间的某段后缀拼上右区间的某段前缀。 这里的某段后缀和前缀显然应该取其能取到的最大值。

然后就是线段树朴实无华的维护了。

inline node merge(node x,node y){
    node k;
    k.mx=max(max(x.mx,y.mx),x.suf+y.pre);//最大子段和
    k.pre=max(x.t+y.pre,x.pre);//最大前缀
    k.suf=max(y.t+x.suf,y.suf);//最大后缀
    k.t=x.t+y.t;//区间和
    return k;
}
node mxsum(int k,int l,int r,int x,int y){//查询
    if(x<=l&&r<=y)return s[k];
    node lres,rres;
    if(x<=mid)lres=mxsum(ls,l,mid,x,y);
    if(y>mid)rres=mxsum(rs,mid+1,r,x,y);
    return merge(lres,rres);//显然需要左区间合并右区间，不能写反了
}

GSS2 - Can you answer these queries II

思路

这题还是比上一道难一些的。
由于维护前后缀最大值显然不支持去重，暴力线段树维护 set 时间当然会炸，所以我们得另辟蹊径。

考虑该如何统计一个区间的答案。如果每次向这个区间的末尾增加一个数，可以发现，每个数将只会对上次出现这个数到当前的区间中造成贡献，贡献的形式是区间加。而区间的答案则是若干次区间加贡献后的历史最大值（可能有点难理解，建议手模一下）。
然后就可以简单地把询问离线下来，挨个查询就行了。
为了防止有人不会维护区间历史最大值，挂个代码。

inline void pushup(int k){
    s[k].mx=max(s[ls].mx,s[rs].mx),s[k].hmx=max(s[ls].hmx,s[rs].hmx);
}
inline void pushdown(int k){
    if(!s[k].lz&&!s[k].hlz)return;
    s[ls].hmx=max(s[ls].hmx,s[ls].mx+s[k].hlz),s[ls].mx+=s[k].lz;
    s[rs].hmx=max(s[rs].hmx,s[rs].mx+s[k].hlz),s[rs].mx+=s[k].lz;
    s[ls].hlz=max(s[ls].hlz,s[ls].lz+s[k].hlz),s[ls].lz+=s[k].lz;
    s[rs].hlz=max(s[rs].hlz,s[rs].lz+s[k].hlz),s[rs].lz+=s[k].lz;
    //维护历史最大值，历史最大tag。
    s[k].hlz=s[k].lz=0;
}

为了防止有人不知道离线思想，也挂个代码：

for(int i=1;i<=m;i++)cin>>q[i].fst.snd>>q[i].fst.fst,q[i].snd=i;
sort(q+1,q+m+1);//按右端点排序
for(int i=1,j=1;i<=m;i++){
    while(j<=q[i].fst.fst)add(1,1,n,p[j],j,a[j]),j++;//处理每增加一个点的贡献
    ans[q[i].snd]=ask(1,1,n,q[i].fst.snd,q[i].fst.fst);
}
for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';

（选讲）GSS3 - Can you answer these queries III

思路

你别告诉我你都会区间查询了还不会单点改。
和普通线段树直接单点改一样。

（选讲）GSS4 - Can you answer these queries IV

思路

没人不会势能线段树吧。
由于每个数不会超过 10^{18}，这意味着最大的数最多只会开 \log\log10^{18}\approx 6 次根号就会变成 1。因此，对于全是 1 和 0 的区间，直接跳过，否则暴力单点改即可。
时间复杂度：O(m\log n\log\log V)。

GSS5 - Can you answer these queries V

思路

细心分讨就行了。

当两区间不交时，显然两区间中间部分肯定是要选的，然后只需要在左区间中找到最大后缀，右区间中找到最大前缀，加起来就完了。
当两区间有交时，事情就有些复杂，要分四种情况。

1. 左端点在右区间取不到的地方，右端点在左区间取不到的地方。
   相当于两区间交集必须取，和之前的情况类似。
2. 左端点在右区间取不到的地方，右端点在左区间取得到的地方。
   需要查询 [x_1,x_2] 的后缀最大加上 (x_2,y_1] 的前缀最大。
3. 左端点在右区间取得到的地方，右端点在左区间取不到的地方。
   需要查询 (y_1,y_2] 的前缀最大加上 [x_2,y_1] 的后缀最大。
4. 左端点在右区间取得到的地方，右端点在左区间取得到的地方。
   直接查询 [x_2,y_1] 的最大子段和。

然后四种情况取个 max 就完了。

为了防止有人听得云里雾里的，放个压行严重的代码：

int getans(int l1,int r1,int l2,int r2){//两区间不交的答案
    return (l1<r1?mxsuf(1,1,n,l1,r1-1).suf:0)+mxsum(1,1,n,r1,l2).t+(l2<r2?mxpre(1,1,n,l2+1,r2).pre:0);
    //注意判断两区间是否存在
}
cin>>l>>r>>x>>y;
if(r<=x)cout<<getans(l,r,x,y)<<'\n';
else cout<<max(max(getans(l,x,x,r),getans(x,r,r,y)),max(getans(l,x,r,y),mxsum(1,1,n,x,r).mx))<<'\n';

GSS6 - Can you answer these queries VI

思路

不说啥了，虽然平衡树可以，但是我不会，所以写了个平衡线段树。
如果想学普通平衡树，应该径直走向题解区。

考虑线段树如何插入。
答案是线段树不能插入，吗？

考虑最简单的情况，整棵线段树只有一个数，我们该如何插入？显然，只需要让那个数变成它的兄弟节点，然后再搞个父亲把它俩连起来就行了。
考虑将上述情况拓展，如果你有很多数该怎么办。我们可以先在线段树中找到插入位置的那个数，接着对它和插入的数经行上述操作即可，代码如下。

inline void insnode(int k,int x,int v){
    int ls=++tot,rs=++tot;//新开两个节点存储（这是动态开点的线段树）
    if(x!=s[k].l)s[rs].sz=1,s[rs].l=s[rs].r=s[k].l+1,chnode(rs,v),s[ls]=s[k];
    //上面的条件是特判插入的数不存在（在n之后），这时候需要把插入的数放在右儿子
    else s[ls].sz=1,s[ls].l=s[ls].r=x,chnode(ls,v),s[rs]=s[k],s[rs].l=s[rs].r=x+1;
    merge(k,ls,rs);//记得把左右儿子合并到这个节点
}

但是该怎么更新线段树的区间下标呢？我们不一定得一次改完，可以写两个类似 pushup、pushdown 的函数一步步改。
所以分为两种情况更新：

1. 自底向上时，我们可以保证左儿子的区间下标是对的（毕竟是在某个数前插入），因此直接把右区间贴到左区间右边，同时更新父亲的右节点即可。代码：

   inline void crtup(int k,int ls,int rs){
   if(!s[ls].sz&&!s[rs].sz)return;//如果没有儿子就没必要更新。
   s[rs].l=s[ls].r+1,s[k].r=s[rs].r=s[ls].r+s[rs].sz;
   }

2. 自顶向下时，我们可以保证父亲的区间下标是对的（毕竟已经更新过了），因此直接把左区间贴到父亲区间左边，右区间贴到父亲区间的右边即可。代码：

   inline void crtdown(int k,int ls,int rs){
   if(!s[ls].sz&&!s[rs].sz)return;//如果没有儿子也没必要更新。
   s[ls].l=s[k].l,s[ls].r=s[k].l+s[ls].sz-1;
   s[rs].l=s[ls].r+1,s[rs].r=s[k].r;
   }

   删除也和插入类似，只需要把这个节点的所有东西还原成最初始的样子就行，代码就不给了。

但要是真这样写，稍微想想就知道，只要一直往一个地方插入，这颗线段树就会退化成一条链，然后时间复杂度就变成 O(n) 了。所以我们需要一种平衡操作来防止这种情况的发生。
考虑一下不平衡的定义，当某棵子树的一个儿子远远大于它的另一个儿子时，这棵树就变得不平衡了。当这个“远远大于”取 3 倍时可以使树高不超过 2\log_2n。
然后分五种情况讨论该如何平衡：

1. 左儿子比右儿子大，左儿子的左儿子比左儿子的右儿子大，如图。 直接让 s[2]=merge(s[5],s[3])，然后 s[1].ls=4,s[1].rs=2 即可。

2. 左儿子比右儿子大，左儿子的左儿子比左儿子的右儿子小，如图。 先 s[2]=merge(s[4],s[6])，再 s[5]=merge(s[7],s[3])，最后 s[1].ls=2,s[1].rs=5 即可。

3. 左儿子比右儿子小，右儿子的左儿子比右儿子的右儿子小，如图。 和情况一类似，只需要 s[3]=merge(s[2],s[4]),s[1].ls=3,s[1].rs=5 即可。

4. 左儿子比右儿子小，右儿子的左儿子比右儿子的右儿子大，如图。 和情况二类似，只需要 s[4]=merge(s[2],s[6]),s[3]=merge(s[7],s[5]),s[1].ls=4 即可。

5. 没有左儿子或右儿子。直接把根节点改为剩下的节点即可。

需要注意的是，一定不能把合并的顺序写错了，代码如下：。

inline void equil(int k){
    int ls=s[k].ls,rs=s[k].rs,x;
    if(!s[ls].sz)return s[k]=s[rs],s[rs].clear();
    if(!s[rs].sz)return s[k]=s[ls],s[ls].clear();
    if(min(s[ls].sz,s[rs].sz)*3>max(s[ls].sz,s[rs].sz))return;
    if(s[ls].sz>s[rs].sz)
        if(s[s[ls].ls].sz>=s[s[ls].rs].sz)s[k].ls=s[ls].ls,merge(ls,s[ls].rs,rs),s[k].rs=ls;
        else x=s[ls].rs,merge(ls,s[ls].ls,s[x].ls),merge(x,s[x].rs,rs),s[k].rs=x;
    else
        if(s[s[rs].ls].sz<=s[s[rs].rs].sz)s[k].rs=s[rs].rs,merge(rs,ls,s[rs].ls),s[k].ls=rs;
        else x=s[rs].ls,merge(rs,s[x].rs,s[rs].rs),merge(x,ls,s[x].ls),s[k].ls=x;
}

然后就完了，值得一提的是，它的常数大大滴小于 FHQ-Treap，甚至小于 Spaly。
为了防止有人完全听不懂，给出完整代码。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
struct node{
    int ls,rs,l,r,sz;
    long long t,mx,pre,suf;
    node(){ls=rs=l=r=t=sz=0,pre=suf=mx=INT_MIN;}
    inline void clear(){l=r=t=sz=0,pre=suf=mx=INT_MIN;}
}s[N<<2];
int tot,n,m,a[N];
inline void crtup(int k,int ls,int rs){
    if(!s[ls].sz&&!s[rs].sz)return;
    s[rs].l=s[ls].r+1,s[k].r=s[rs].r=s[ls].r+s[rs].sz;
}
inline void crtdown(int k,int ls,int rs){
    if(!s[ls].sz&&!s[rs].sz)return;
    s[ls].l=s[k].l,s[ls].r=s[k].l+s[ls].sz-1;
    s[rs].l=s[ls].r+1,s[rs].r=s[k].r;
}
inline node merge(int k,int x,int y){
    crtup(k,x,y);
    s[k].l=s[x].l,s[k].r=s[y].r,s[k].sz=s[k].r-s[k].l+1,s[k].ls=x,s[k].rs=y;
    s[k].mx=max(max(s[x].mx,s[y].mx),s[x].suf+s[y].pre);
    s[k].pre=max(s[x].t+s[y].pre,s[x].pre);
    s[k].suf=max(s[y].t+s[x].suf,s[y].suf);
    s[k].t=s[x].t+s[y].t;
    return s[k];
}
inline node merge(node x,node y){
    node k;
    k.mx=max(max(x.mx,y.mx),x.suf+y.pre);
    k.pre=max(x.t+y.pre,x.pre);
    k.suf=max(y.t+x.suf,y.suf);
    k.t=x.t+y.t;
    return k;
}
inline void equil(int k){
    int ls=s[k].ls,rs=s[k].rs,x;
    if(!s[ls].sz)return s[k]=s[rs],s[rs].clear();
    if(!s[rs].sz)return s[k]=s[ls],s[ls].clear();
    if(min(s[ls].sz,s[rs].sz)*3>max(s[ls].sz,s[rs].sz))return;
    if(s[ls].sz>s[rs].sz)
        if(s[s[ls].ls].sz>=s[s[ls].rs].sz)s[k].ls=s[ls].ls,merge(ls,s[ls].rs,rs),s[k].rs=ls;
        else x=s[ls].rs,merge(ls,s[ls].ls,s[x].ls),merge(x,s[x].rs,rs),s[k].rs=x;
    else
        if(s[s[rs].ls].sz<=s[s[rs].rs].sz)s[k].rs=s[rs].rs,merge(rs,ls,s[rs].ls),s[k].ls=rs;
        else x=s[rs].ls,merge(rs,s[x].rs,s[rs].rs),merge(x,ls,s[x].ls),s[k].ls=x;
}
inline void chnode(int k,int v){
    s[k].mx=s[k].pre=s[k].suf=s[k].t=v;
}
inline void insnode(int k,int x,int v){
    int ls=++tot,rs=++tot;
    if(x!=s[k].l)s[rs].sz=1,s[rs].l=s[rs].r=s[k].l+1,chnode(rs,v),s[ls]=s[k];
    else s[ls].sz=1,s[ls].l=s[ls].r=x,chnode(ls,v),s[rs]=s[k],s[rs].l=s[rs].r=x+1;
    merge(k,ls,rs);
}
#define mid s[ls].r
#define ls s[k].ls
#define rs s[k].rs
void build(int k,int l,int r){
    s[k].l=l,s[k].r=r;
    if(l==r)return chnode(k,a[l]),s[k].sz=1,void();
    ls=k<<1,rs=k<<1|1,build(ls,l,(l+r)>>1),build(rs,((l+r)>>1)+1,r);
    merge(k,ls,rs);
}
void ins(int k,int x,int v){
    crtdown(k,ls,rs);
    if(s[k].l==s[k].r)return insnode(k,x,v),void();
    if(x<=mid)ins(ls,x,v);
    else ins(rs,x,v);
    merge(k,ls,rs),equil(k);
}
void del(int k,int x){
    crtdown(k,ls,rs);
    if(s[k].l==s[k].r)return s[k].clear();
    if(x<=mid)del(ls,x);
    else del(rs,x);
    merge(k,ls,rs),equil(k);
}
void change(int k,int x,int v){
    crtdown(k,ls,rs);
    if(s[k].l==s[k].r)return chnode(k,v);
    if(x<=mid)change(ls,x,v);
    else change(rs,x,v);
    merge(k,ls,rs);
}
node mxsum(int k,int x,int y){
    crtdown(k,ls,rs);
    if(x<=s[k].l&&s[k].r<=y)return s[k];
    node lres,rres;
    if(x<=mid)lres=mxsum(ls,x,y);
    if(y>mid)rres=mxsum(rs,x,y);
    return merge(lres,rres);
}
char op;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n),tot=n<<2,cin>>m;
    for(int i=1,x,y;i<=m;i++){
        cin>>op>>x;
        switch(op){
            case 'I':cin>>y,ins(1,x,y);break;
            case 'D':del(1,x);break;
            case 'R':cin>>y,change(1,x,y);break;
            case 'Q':cin>>y,cout<<mxsum(1,x,y).mx<<'\n';break;
        }
    }
    return 0;
}

后话：现在知道这玩意叫做 Weight Balanced Leafy Tree。

（选讲）GSS7 - Can you answer these queries VII

思路

这不就树剖模板加线段树模板吗？

树剖就不多说了，区间修改也很简单，查最大子段和相信各位也会了，所以就把它们混在一起就行了。

简单说几个坑点：

1. 最大子段和要和 0 取 \max，这意味着在 pushdown 时，最大前缀和最大后缀也要和 0 取 \max。
2. 树上修改没啥，但是树上合并一定要注意顺序。

好像就没啥了，给出查询的代码：

inline node rev(node x){
    return swap(x.pre,x.suf),x;//反转区间相当于交换前后缀最大值
}
inline int ask(int x,int y){
    node resx,resy;
    while(top[x]!=top[y]){
        if(dep[top[x]]>dep[top[y]])merge(resx,ask(1,1,n,dfn[top[x]],dfn[x]),resx),x=fa[top[x]];
        else merge(resy,ask(1,1,n,dfn[top[y]],dfn[y]),resy),y=fa[top[y]];
    }
    if(dep[x]>dep[y])return merge(resx,rev(merge(resx,ask(1,1,n,dfn[y],dfn[x]),resx)),resy).res;
    else return merge(resy,rev(merge(resy,ask(1,1,n,dfn[x],dfn[y]),resy)),resx).res;
    //注意反转resx或resy
}

GSS8 - Can you answer these queries VIII

思路

好吧，确实和 GSS6 大差不差。

线段树显然不能直接维护查询的式子，还是先想想该怎么把它化简一下。

令 f(l,r,k)=\sum\limits_{i=l}^{r}a_i(i-l+1)^k（取模这东西很简单，我们先丢掉）。
首先，我们得先搞出一个 mid，然后线段树才能合并。于是就化成了：

发现左边是 f(l,mid,k)，可以直接转移贡献，所以继续化简右边。
于是再在右边搞一个 mid。

发现右边小括号中出现了 i-mid=i-(mid+1)+1，因此使用二项式定理裂项。

然后就可以把中间的一些式子提出来。

接着就会发现右边是 f(mid+1,r,j)。

前面的系数在预处理组合数后可以 O(k^2) 暴力求。
好了，代码实现的 merge 函数：

inline node merge(node x,node y){
    node k;
    k.sz=x.sz+y.sz,p[0]=1;//p是预处理左区间的幂次
    for(int i=1;i<K;i++)p[i]=p[i-1]*x.sz;
    for(int i=0;i<K;i++){
        k.t[i]=x.t[i];//先加上左区间的答案
        for(int j=0;j<=i;j++)k.t[i]+=C[i][j]*p[i-j]*y.t[j];
        //暴力算右区间的贡献
    }
    return k;
}

然后是单点修改。
不过比较简单，因为线段树直接维护的 k 个答案，所以只用把所有的答案改成 v 就行了。

至于插入删除，套一下 GSS6 代码就行了。

题外话，WBLT 常数真的很小。

完结撒花