SPOJ GSS 系列简要题解

博主： M_sea
发布时间：2019 年 08 月 06 日
3678次浏览
3 条评论
21842字数
分类：题解

GSS1

线段树上维护以下 $4$ 个东西：

区间和
区间最大前缀和
区间最大后缀和
区间最大子段和

合并两个区间应该比较简单，这里不再赘述。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;

int n,Q,a[N];

struct node { int sum,lmax,rmax,ans; };
node operator +(node a,node b) {
    node c;
    c.sum=a.sum+b.sum;
    c.lmax=max(a.lmax,a.sum+b.lmax);
    c.rmax=max(b.rmax,b.sum+a.rmax);
    c.ans=max(max(a.ans,b.ans),a.rmax+b.lmax);
    return c;
}

#define ls (o<<1)
#define rs (o<<1|1)
node t[N<<2];
inline void build(int o,int l,int r) {
    if (l==r) {
        t[o].sum=t[o].lmax=t[o].rmax=t[o].ans=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    t[o]=t[ls]+t[rs];
}
inline node query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return t[o];
    int mid=(l+r)>>1;
    if (qr<=mid) return query(ls,l,mid,ql,qr);
    else if (ql>mid) return query(rs,mid+1,r,ql,qr);
    else return query(ls,l,mid,ql,mid)+query(rs,mid+1,r,mid+1,qr);
}
#undef ls
#undef rs

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    build(1,1,n);
    Q=read();
    while (Q--) {
        int l=read(),r=read();
        printf("%d\n",query(1,1,n,l,r).ans);
    }
    return 0;
}

GSS2

这题就很神仙了。

把所有询问离线并按右端点排序，然后从左往右扫。

对于线段树的每个叶子节点 $[i,i]$，假设当前扫到了 $p$ ，那么该节点存的是 $\displaystyle\sum_{j=i}^pa_j$ 。

设 $pre_i$ 表示上一个和 $a_i$ 相同的数，那么每次把 $[pre_i+1,i]$ 加上 $a+i$ 即可。

再额外维护一个历史最大值，这样子扫到 $r$ 时就只要询问 $[l,r]$ 的历史最大值的最大值就可以得到答案了。

那么线段树维护这些东西即可：

和
和的历史最大值
和的懒标记
和的历史最大值的懒标记

合并两个区间应该也比较简单，详见代码。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q,a[N];

#define ls (o<<1)
#define rs (o<<1|1)
int now_mx[N<<2],now_lz[N<<2],his_mx[N<<2],his_lz[N<<2];

inline void pushup(int o) {
    now_mx[o]=max(now_mx[ls],now_mx[rs]);
    his_mx[o]=max(his_mx[ls],his_mx[rs]);
}
inline void pushdown(int o) {
    his_mx[ls]=max(his_mx[ls],now_mx[ls]+his_lz[o]);
    his_lz[ls]=max(his_lz[ls],now_lz[ls]+his_lz[o]);
    now_mx[ls]+=now_lz[o],now_lz[ls]+=now_lz[o];
    his_mx[rs]=max(his_mx[rs],now_mx[rs]+his_lz[o]);
    his_lz[rs]=max(his_lz[rs],now_lz[rs]+his_lz[o]);
    now_mx[rs]+=now_lz[o],now_lz[rs]+=now_lz[o];
    his_lz[o]=now_lz[o]=0;
}
inline void modify(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) {
        now_mx[o]+=w,now_lz[o]+=w;
        his_mx[o]=max(his_mx[o],now_mx[o]);
        his_lz[o]=max(his_lz[o],now_lz[o]);
        return;
    }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
inline int query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return his_mx[o];
    int mid=(l+r)>>1,res=0; pushdown(o); 
    if (ql<=mid) res=max(res,query(ls,l,mid,ql,qr));
    if (qr>mid) res=max(res,query(rs,mid+1,r,ql,qr));
    pushup(o); return res;
}
#undef ls
#undef rs

int pre[N],pos[N<<1],ans[N];
struct Query { int id,l,r; } q[N];
bool operator <(Query a,Query b) { return a.r<b.r; }

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i) pre[i]=pos[a[i]+N],pos[a[i]+N]=i;
    Q=read();
    for (re int i=1;i<=Q;++i) q[i]=(Query){i,read(),read()};
    sort(q+1,q+Q+1);
    for (re int i=1,j=1;i<=n;++i) {
        modify(1,1,n,pre[i]+1,i,a[i]);
        while (q[j].r==i) ans[q[j].id]=query(1,1,n,q[j].l,i),++j;
    }
    for (re int i=1;i<=Q;++i) printf("%d\n",ans[i]);
    return 0;
}

GSS3

就是 GSS1 加个修改操作，没什么好说的。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;

int n,Q,a[N];

struct node { int sum,lmax,rmax,ans; };
node operator +(node a,node b) {
    node c;
    c.sum=a.sum+b.sum;
    c.lmax=max(a.lmax,a.sum+b.lmax);
    c.rmax=max(b.rmax,b.sum+a.rmax);
    c.ans=max(max(a.ans,b.ans),a.rmax+b.lmax);
    return c;
}

#define ls (o<<1)
#define rs (o<<1|1)
node t[N<<2];
inline void build(int o,int l,int r) {
    if (l==r) {
        t[o].sum=t[o].lmax=t[o].rmax=t[o].ans=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    t[o]=t[ls]+t[rs];
}
inline void modify(int o,int l,int r,int p,int w) {
    if (l==r) {
        t[o].sum=t[o].lmax=t[o].rmax=t[o].ans=w;
        return;
    }
    int mid=(l+r)>>1;
    if (p<=mid) modify(ls,l,mid,p,w);
    else modify(rs,mid+1,r,p,w);
    t[o]=t[ls]+t[rs];
}
inline node query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return t[o];
    int mid=(l+r)>>1;
    if (qr<=mid) return query(ls,l,mid,ql,qr);
    else if (ql>mid) return query(rs,mid+1,r,ql,qr);
    else return query(ls,l,mid,ql,mid)+query(rs,mid+1,r,mid+1,qr);
}
#undef ls
#undef rs

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    build(1,1,n);
    Q=read();
    while (Q--) {
        int op=read(),l=read(),r=read();
        if (!op) modify(1,1,n,l,r);
        else printf("%d\n",query(1,1,n,l,r).ans);
    }
    return 0;
}

事实上这题可以动态 DP ，点我。（当然 GSS1 也是可以动态 DP 的。）

GSS4

用线段树维护区间和。

注意到一个数开根号变成 $1$ 的次数不大，而变成 $1$ 后就不用修改了。

假设现在在修改一个区间：如果该区间内的所有数开根号都不会变了，那就不修改了；否则直接暴力修改到叶节点即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q;

#define ls (o<<1)
#define rs (o<<1|1)
int sum[N<<2],f[N<<2];
inline void pushup(int o) { sum[o]=sum[ls]+sum[rs],f[o]=f[ls]&f[rs]; }
inline void build(int o,int l,int r) {
    if (l==r) { sum[o]=read(),f[o]=sum[o]<=1; return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
inline void modify(int o,int l,int r,int ql,int qr) {
    if (f[o]) return;
    if (l==r) {
        sum[o]=floor(sqrt(sum[o]));
        if (sum[o]<=1) f[o]=1;
        return;
    }
    int mid=(l+r)>>1;
    if (ql<=mid) modify(ls,l,mid,ql,qr);
    if (qr>mid) modify(rs,mid+1,r,ql,qr);
    pushup(o);
}
inline int query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return sum[o];
    int mid=(l+r)>>1,res=0;
    if (ql<=mid) res+=query(ls,l,mid,ql,qr);
    if (qr>mid) res+=query(rs,mid+1,r,ql,qr);
    return res;
}
#undef ls
#undef rs

signed main() {
    int T=0;
    while (scanf("%lld",&n)==1) {
        build(1,1,n); Q=read();
        printf("Case #%lld:\n",++T);
        while (Q--) {
            int op=read(),l=read(),r=read();
            if (l>r) swap(l,r);
            if (op) printf("%lld\n",query(1,1,n,l,r));
            else modify(1,1,n,l,r);
        }
        puts("");
    }
    return 0;
}

GSS5

在 GSS1 的基础上大力讨论一下即可。

如果两区间没有交，答案就是 $[x_1,y_1]$ 的最大后缀和加 $(y_1,x_2)$ 的和加 $[x_2,y_2]$ 的最大前缀和。
如果两区间有交，答案为以下三者中的最大值：
- $[x_2,y_1]$ 的最大子段和。
- $[x_1,x_2)$ 的最大后缀和加 $[x_2,y_2]$ 的最大前缀和。
- $[x_1,y_1]$ 的最大后缀和加 $(y_1,y_2]$ 的最大后缀和。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10;

int n,Q,a[N];

struct node { int sum,lmax,rmax,ans; };
node operator +(node a,node b) {
    node c;
    c.sum=a.sum+b.sum;
    c.lmax=max(a.lmax,a.sum+b.lmax);
    c.rmax=max(b.rmax,b.sum+a.rmax);
    c.ans=max(max(a.ans,b.ans),a.rmax+b.lmax);
    return c;
}

#define ls (o<<1)
#define rs (o<<1|1)
node t[N<<2];
inline void build(int o,int l,int r) {
    if (l==r) {
        t[o].sum=t[o].lmax=t[o].rmax=t[o].ans=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    t[o]=t[ls]+t[rs];
}
inline node query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return t[o];
    int mid=(l+r)>>1;
    if (qr<=mid) return query(ls,l,mid,ql,qr);
    else if (ql>mid) return query(rs,mid+1,r,ql,qr);
    else return query(ls,l,mid,ql,mid)+query(rs,mid+1,r,mid+1,qr);
}
#undef ls
#undef rs

inline int calc(int l1,int r1,int l2,int r2) {
    int res;
    if (r1<l2) {
        res=query(1,1,n,l1,r1).rmax;
        res+=query(1,1,n,l2,r2).lmax;
        if (r1+1<l2)res+=query(1,1,n,r1+1,l2-1).sum;
    } else {
        res=query(1,1,n,l2,r1).ans;
        res=max(res,query(1,1,n,l1,l2).rmax+query(1,1,n,l2,r2).lmax-a[l2]);
        res=max(res,query(1,1,n,l1,r1).rmax+query(1,1,n,r1,r2).lmax-a[r1]);
    }
    return res;
}

int main() {
    int T=read();
    while (T--) {
        n=read();
        for (re int i=1;i<=n;++i) a[i]=read();
        build(1,1,n);
        Q=read();
        while (Q--) {
            int l1=read(),r1=read(),l2=read(),r2=read();
            printf("%d\n",calc(l1,r1,l2,r2));
        }
    }
    return 0;
}

GSS6

在 GSS1 的基础上把线段树改成平衡树即可。

插入、删除、修改、查询就是基础的平衡树操作。

然后 pushup 和线段树有些不同，但本质是一样的。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,Q,a[N];

// fhq treap
int root,tot=0;
int ch[N][2],val[N],rnd[N],sz[N];
struct node { int sum,lmax,rmax,ans; } t[N];

inline int new_node(int w) {
    ++tot;
    sz[tot]=1,val[tot]=w,rnd[tot]=rand();
    t[tot].lmax=t[tot].rmax=max(w,0);
    t[tot].sum=t[tot].ans=w;
    return tot;
}
inline void pushup(int x) {
    int ls=ch[x][0],rs=ch[x][1];
    sz[x]=sz[ls]+sz[rs]+1;
    t[x].sum=t[ls].sum+val[x]+t[rs].sum;
    t[x].lmax=max(t[ls].lmax,t[ls].sum+val[x]+t[rs].lmax);
    t[x].rmax=max(t[rs].rmax,t[rs].sum+val[x]+t[ls].rmax);
    t[x].ans=max(max(t[ls].ans,t[rs].ans),t[ls].rmax+val[x]+t[rs].lmax);
}
inline void split(int o,int k,int& x,int& y) {
    if (!o) { x=y=0; return; }
    if (k<=sz[ch[o][0]]) y=o,split(ch[o][0],k,x,ch[o][0]);
    else x=o,split(ch[o][1],k-sz[ch[o][0]]-1,ch[o][1],y);
    pushup(o);
}
inline int merge(int A,int B) {
    if (!A||!B) return A+B;
    if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B),pushup(A); return A; }
    else { ch[B][0]=merge(A,ch[B][0]),pushup(B); return B; }
}

int main() {
    srand(19260817);
    n=read(); t[0].ans=-2e9;
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i) root=merge(root,new_node(a[i]));
    Q=read();
    while (Q--) {
        char op[2]; scanf("%s",op);
        int o,r,z;
        if (op[0]=='I') {
            int p=read(),x=read();
            split(root,p-1,o,r);
            root=merge(o,merge(new_node(x),r));
        } else if (op[0]=='D') {
            int p=read();
            split(root,p-1,o,r),split(r,1,r,z);
            root=merge(o,z);
        } else if (op[0]=='R') {
            int p=read(),x=read();
            split(root,p-1,o,r),split(r,1,r,z);
            val[r]=x,pushup(r);
            root=merge(o,merge(r,z));
        } else {
            int L=read(),R=read();
            split(root,R,r,z),split(r,L-1,o,r);
            printf("%d\n",t[r].ans);
            root=merge(o,merge(r,z));
        }
    }
    return 0;
}

GSS7

在 GSS1 的基础上加个树链剖分即可。

首先解决区间修改的问题，每个节点维护一个区间赋值标记即可。

链修改比较简单，把所有重链都改一遍即可。

需要注意的是链查询。因为合并两个区间时左右顺序对结果是有影响的，所以不能直接合并过去。

一种方法是维护一个 $L$ 和一个 $R$ ，分别代表左右两条链合并的结果，最后再把 $L,R$ 并起来。

写代码的时候要考虑清楚左右顺序问题，我因为这个 WA 了几发。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q,a[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int fa[N],dep[N],sz[N],hson[N],top[N];
int dfn[N],id[N],tim;
inline void dfs1(int u,int f) {
    fa[u]=f,dep[u]=dep[f]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
inline void dfs2(int u,int anc) {
    top[u]=anc,dfn[u]=++tim,id[tim]=u;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}

#define ls (o<<1)
#define rs (o<<1|1)
struct node {
    int sum,lmax,rmax,ans,flag,setv;
    node() { sum=lmax=rmax=ans=flag=setv=0; }
} t[N<<2];
node operator +(node a,node b) {
    node c;
    c.sum=a.sum+b.sum;
    c.lmax=max(a.lmax,a.sum+b.lmax);
    c.rmax=max(b.rmax,b.sum+a.rmax);
    c.ans=max(max(a.ans,b.ans),a.rmax+b.lmax);
    c.flag=c.setv=0;
    return c;
}
inline void update(int o,int l,int r,int w) {
    t[o].sum=(r-l+1)*w;
    t[o].lmax=t[o].rmax=t[o].ans=max(t[o].sum,0);
    t[o].flag=1,t[o].setv=w;
}
inline void pushup(int o) { t[o]=t[ls]+t[rs]; }
inline void pushdown(int o,int l,int r) {
    if (t[o].flag) {
        int mid=(l+r)>>1;
        update(ls,l,mid,t[o].setv);
        update(rs,mid+1,r,t[o].setv);
        t[o].flag=t[o].setv=0;
    }
}
inline void build(int o,int l,int r) {
    if (l==r) {
        t[o].sum=a[id[l]];
        t[o].lmax=t[o].rmax=t[o].ans=max(t[o].sum,0);
        t[o].flag=t[o].setv=0;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
inline void modify(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) { update(o,l,r,w); return; }
    int mid=(l+r)>>1; pushdown(o,l,r);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
inline node query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return t[o];
    int mid=(l+r)>>1; node res; pushdown(o,l,r);
    if (ql<=mid) res=res+query(ls,l,mid,ql,qr);
    if (qr>mid) res=res+query(rs,mid+1,r,ql,qr);
    pushup(o); return res;
}
#undef ls
#undef rs

inline void chain_modify(int u,int v,int w) {
    int tu=top[u],tv=top[v];
    while (tu!=tv) {
        if (dep[tu]<dep[tv]) swap(u,v),swap(tu,tv);
        modify(1,1,n,dfn[tu],dfn[u],w);
        u=fa[tu],tu=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    modify(1,1,n,dfn[v],dfn[u],w);
}
inline int chain_query(int u,int v) {
    node L,R; int tu=top[u],tv=top[v];
    while (tu!=tv) {
        if (dep[tu]<dep[tv]) {
            R=query(1,1,n,dfn[tv],dfn[v])+R;
            v=fa[tv],tv=top[v];
        } else {
            L=query(1,1,n,dfn[tu],dfn[u])+L;
            u=fa[tu],tu=top[u];
        }
    }
    if (dep[u]<dep[v]) R=query(1,1,n,dfn[u],dfn[v])+R;
    else L=query(1,1,n,dfn[v],dfn[u])+L;
    swap(L.lmax,L.rmax); return (L+R).ans;
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs1(1,0),dfs2(1,1),build(1,1,n);
    Q=read();
    while (Q--) {
        int op=read();
        if (op==1) {
            int u=read(),v=read();
            printf("%d\n",chain_query(u,v));
        } else {
            int u=read(),v=read(),w=read();
            chain_modify(u,v,w);
        }
    }
    return 0;
}

GSS8

感觉还是有点难。

首先这个操作显然用平衡树维护。

注意到 $k$ 很小，考虑每个节点对于每个 $k$ 都维护一个 $ans$ 。

考虑怎么合并两个区间的信息：
$$
\begin{aligned}
\sum_{i=l}^ra_i(i-l+1)^k&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{i=mid+1}^ra_i(i-l+1)^k\right)\\
&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{i=mid+1}^ra_i\big((mid-l+1)-(i-mid)\big)^k\right)\\
&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{i=mid+1}^ra_i\sum_{j=0}^k{k\choose j}(mid-l+1)^{k-j}(i-mid)^{j}\right)\\
&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{j=0}^k{k\choose j}(mid-l+1)^{k-j}\sum_{i=mid+1}^ra_i(i-mid)^{j}\right)\\
&=lans_k+\left(\sum_{j=0}^k{k\choose j}(mid-l+1)^{k-j}rans_j\right)
\end{aligned}
$$
这样子就很好合并了。

然后因为是平衡树，所以直接把当前节点丢到左区间（或右区间）去，然后就是两个区间合并了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
#define int unsigned int

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10,K=10+10;

int n,Q;
int C[K][K];

inline void init() {
    srand(19260817);
    for (re int i=C[0][0]=1;i<=10;++i)
        for (re int j=C[i][0]=1;j<=i;++j)
            C[i][j]=C[i-1][j]+C[i-1][j-1];
}

// fhq treap
int root,tot=0;
int ch[N][2],sz[N],val[N],rnd[N];
int ans[N][K],pw[K];

inline int newnode(int w) {
    ++tot;
    sz[tot]=1,val[tot]=w,rnd[tot]=rand();
    for (re int i=0;i<=10;++i) ans[tot][i]=w;
    return tot;
}
inline void pushup(int x) {
    int ls=ch[x][0],rs=ch[x][1];
    sz[x]=sz[ls]+sz[rs]+1;
    for (re int i=pw[0]=1;i<=10;++i) pw[i]=pw[i-1]*(sz[ls]+1);
    for (re int k=0;k<=10;++k) {
        ans[x][k]=ans[ls][k]+val[x]*pw[k];
        for (re int i=0;i<=k;++i) ans[x][k]+=C[k][i]*pw[k-i]*ans[rs][i];
    }
}
inline void split(int o,int k,int& x,int& y) {
    if (!o) { x=y=0; return; }
    if (k<=sz[ch[o][0]]) y=o,split(ch[o][0],k,x,ch[o][0]);
    else x=o,split(ch[o][1],k-sz[ch[o][0]]-1,ch[o][1],y);
    pushup(o);
}
inline int merge(int A,int B) {
    if (!A||!B) return A+B;
    if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B),pushup(A); return A; }
    else { ch[B][0]=merge(A,ch[B][0]),pushup(B); return B; }
}

signed main() {
    init();
    n=read();
    for (re int i=1;i<=n;++i) root=merge(root,newnode(read()));
    Q=read();
    while (Q--) {
        char op[2]; scanf("%s",op);
        int o,r,z;
        if (op[0]=='I') {
            int p=read()+1,w=read();
            split(root,p-1,o,r);
            root=merge(merge(o,newnode(w)),r);
        } else if (op[0]=='D') {
            int p=read()+1;
            split(root,p-1,o,r),split(r,1,r,z);
            root=merge(o,z);
        } else if (op[0]=='R') {
            int p=read()+1,w=read();
            split(root,p-1,o,r),split(r,1,r,z);
            val[r]=w,pushup(r);
            root=merge(merge(o,r),z);
        } else {
            int L=read()+1,R=read()+1,k=read();
            split(root,L-1,o,r),split(r,R-L+1,r,z);
            printf("%u\n",ans[r][k]);
            root=merge(merge(o,r),z);
        }
    }
    return 0;
}

最后修改：2019 年 09 月 27 日 01 : 43 PM

发表评论取消回复

评论 *

私密评论

名称 *

邮箱 *

地址

3 条评论

smy
August 6th, 2019 at 12:09 am

怎么这么快

回复
1. M_sea
  August 6th, 2019 at 07:07 am
  
  @smy
  
  感觉除了 GSS2 和 GSS8 都挺不要脑子的啊...
  
  回复
  1. smy
    August 6th, 2019 at 01:12 pm
    
    @M_sea
    
    您好强啊qwq
    
    回复

洛谷5176 公约数
浏览次数: 25551
HNOI2019 ～Zero～
浏览次数: 25344
APIO2020 ～Intermezzo～
浏览次数: 14535
～After OI～
浏览次数: 14408
CSP2019 ～Idle Dream～
浏览次数: 9838

草莓奶昔
一直在研究这道题，难得有这么好的码风，感谢楼主!!!
konjacq
巨佬M_sea的AFO就是去搞ACM吗orz
xgzc
现在已经拿到满意的成绩了
Qihoo360
orz
智子
突然想起我小学时也是在白老师那里学的（

CF520E Pluses everywhere
浏览次数: 1105
～After OI～
浏览次数: 14408
洛谷5025 [SNOI2017]炸弹
浏览次数: 1241
洛谷6773 [NOI2020]命运
浏览次数: 1694
洛谷1173 [NOI2016]网格
浏览次数: 1578

SPOJ GSS 系列简要题解

M_sea • 2019 年 08 月 06 日

GSS1

线段树上维护以下 $4$ 个东西：

区间和
区间最大前缀和
区间最大后缀和
区间最大子段和

合并两个区间应该比较简单，这里不再赘述。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;

int n,Q,a[N];

struct node { int sum,lmax,rmax,ans; };
node operator +(node a,node b) {
    node c;
    c.sum=a.sum+b.sum;
    c.lmax=max(a.lmax,a.sum+b.lmax);
    c.rmax=max(b.rmax,b.sum+a.rmax);
    c.ans=max(max(a.ans,b.ans),a.rmax+b.lmax);
    return c;
}

#define ls (o<<1)
#define rs (o<<1|1)
node t[N<<2];
inline void build(int o,int l,int r) {
    if (l==r) {
        t[o].sum=t[o].lmax=t[o].rmax=t[o].ans=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    t[o]=t[ls]+t[rs];
}
inline node query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return t[o];
    int mid=(l+r)>>1;
    if (qr<=mid) return query(ls,l,mid,ql,qr);
    else if (ql>mid) return query(rs,mid+1,r,ql,qr);
    else return query(ls,l,mid,ql,mid)+query(rs,mid+1,r,mid+1,qr);
}
#undef ls
#undef rs

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    build(1,1,n);
    Q=read();
    while (Q--) {
        int l=read(),r=read();
        printf("%d\n",query(1,1,n,l,r).ans);
    }
    return 0;
}

GSS2

这题就很神仙了。

把所有询问离线并按右端点排序，然后从左往右扫。

对于线段树的每个叶子节点 $[i,i]$，假设当前扫到了 $p$ ，那么该节点存的是 $\displaystyle\sum_{j=i}^pa_j$ 。

设 $pre_i$ 表示上一个和 $a_i$ 相同的数，那么每次把 $[pre_i+1,i]$ 加上 $a+i$ 即可。

再额外维护一个历史最大值，这样子扫到 $r$ 时就只要询问 $[l,r]$ 的历史最大值的最大值就可以得到答案了。

那么线段树维护这些东西即可：

和
和的历史最大值
和的懒标记
和的历史最大值的懒标记

合并两个区间应该也比较简单，详见代码。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q,a[N];

#define ls (o<<1)
#define rs (o<<1|1)
int now_mx[N<<2],now_lz[N<<2],his_mx[N<<2],his_lz[N<<2];

inline void pushup(int o) {
    now_mx[o]=max(now_mx[ls],now_mx[rs]);
    his_mx[o]=max(his_mx[ls],his_mx[rs]);
}
inline void pushdown(int o) {
    his_mx[ls]=max(his_mx[ls],now_mx[ls]+his_lz[o]);
    his_lz[ls]=max(his_lz[ls],now_lz[ls]+his_lz[o]);
    now_mx[ls]+=now_lz[o],now_lz[ls]+=now_lz[o];
    his_mx[rs]=max(his_mx[rs],now_mx[rs]+his_lz[o]);
    his_lz[rs]=max(his_lz[rs],now_lz[rs]+his_lz[o]);
    now_mx[rs]+=now_lz[o],now_lz[rs]+=now_lz[o];
    his_lz[o]=now_lz[o]=0;
}
inline void modify(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) {
        now_mx[o]+=w,now_lz[o]+=w;
        his_mx[o]=max(his_mx[o],now_mx[o]);
        his_lz[o]=max(his_lz[o],now_lz[o]);
        return;
    }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
inline int query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return his_mx[o];
    int mid=(l+r)>>1,res=0; pushdown(o); 
    if (ql<=mid) res=max(res,query(ls,l,mid,ql,qr));
    if (qr>mid) res=max(res,query(rs,mid+1,r,ql,qr));
    pushup(o); return res;
}
#undef ls
#undef rs

int pre[N],pos[N<<1],ans[N];
struct Query { int id,l,r; } q[N];
bool operator <(Query a,Query b) { return a.r<b.r; }

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i) pre[i]=pos[a[i]+N],pos[a[i]+N]=i;
    Q=read();
    for (re int i=1;i<=Q;++i) q[i]=(Query){i,read(),read()};
    sort(q+1,q+Q+1);
    for (re int i=1,j=1;i<=n;++i) {
        modify(1,1,n,pre[i]+1,i,a[i]);
        while (q[j].r==i) ans[q[j].id]=query(1,1,n,q[j].l,i),++j;
    }
    for (re int i=1;i<=Q;++i) printf("%d\n",ans[i]);
    return 0;
}

GSS3

就是 GSS1 加个修改操作，没什么好说的。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;

int n,Q,a[N];

struct node { int sum,lmax,rmax,ans; };
node operator +(node a,node b) {
    node c;
    c.sum=a.sum+b.sum;
    c.lmax=max(a.lmax,a.sum+b.lmax);
    c.rmax=max(b.rmax,b.sum+a.rmax);
    c.ans=max(max(a.ans,b.ans),a.rmax+b.lmax);
    return c;
}

#define ls (o<<1)
#define rs (o<<1|1)
node t[N<<2];
inline void build(int o,int l,int r) {
    if (l==r) {
        t[o].sum=t[o].lmax=t[o].rmax=t[o].ans=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    t[o]=t[ls]+t[rs];
}
inline void modify(int o,int l,int r,int p,int w) {
    if (l==r) {
        t[o].sum=t[o].lmax=t[o].rmax=t[o].ans=w;
        return;
    }
    int mid=(l+r)>>1;
    if (p<=mid) modify(ls,l,mid,p,w);
    else modify(rs,mid+1,r,p,w);
    t[o]=t[ls]+t[rs];
}
inline node query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return t[o];
    int mid=(l+r)>>1;
    if (qr<=mid) return query(ls,l,mid,ql,qr);
    else if (ql>mid) return query(rs,mid+1,r,ql,qr);
    else return query(ls,l,mid,ql,mid)+query(rs,mid+1,r,mid+1,qr);
}
#undef ls
#undef rs

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    build(1,1,n);
    Q=read();
    while (Q--) {
        int op=read(),l=read(),r=read();
        if (!op) modify(1,1,n,l,r);
        else printf("%d\n",query(1,1,n,l,r).ans);
    }
    return 0;
}

事实上这题可以动态 DP ，点我。（当然 GSS1 也是可以动态 DP 的。）

GSS4

用线段树维护区间和。

注意到一个数开根号变成 $1$ 的次数不大，而变成 $1$ 后就不用修改了。

假设现在在修改一个区间：如果该区间内的所有数开根号都不会变了，那就不修改了；否则直接暴力修改到叶节点即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q;

#define ls (o<<1)
#define rs (o<<1|1)
int sum[N<<2],f[N<<2];
inline void pushup(int o) { sum[o]=sum[ls]+sum[rs],f[o]=f[ls]&f[rs]; }
inline void build(int o,int l,int r) {
    if (l==r) { sum[o]=read(),f[o]=sum[o]<=1; return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
inline void modify(int o,int l,int r,int ql,int qr) {
    if (f[o]) return;
    if (l==r) {
        sum[o]=floor(sqrt(sum[o]));
        if (sum[o]<=1) f[o]=1;
        return;
    }
    int mid=(l+r)>>1;
    if (ql<=mid) modify(ls,l,mid,ql,qr);
    if (qr>mid) modify(rs,mid+1,r,ql,qr);
    pushup(o);
}
inline int query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return sum[o];
    int mid=(l+r)>>1,res=0;
    if (ql<=mid) res+=query(ls,l,mid,ql,qr);
    if (qr>mid) res+=query(rs,mid+1,r,ql,qr);
    return res;
}
#undef ls
#undef rs

signed main() {
    int T=0;
    while (scanf("%lld",&n)==1) {
        build(1,1,n); Q=read();
        printf("Case #%lld:\n",++T);
        while (Q--) {
            int op=read(),l=read(),r=read();
            if (l>r) swap(l,r);
            if (op) printf("%lld\n",query(1,1,n,l,r));
            else modify(1,1,n,l,r);
        }
        puts("");
    }
    return 0;
}

GSS5

在 GSS1 的基础上大力讨论一下即可。

如果两区间没有交，答案就是 $[x_1,y_1]$ 的最大后缀和加 $(y_1,x_2)$ 的和加 $[x_2,y_2]$ 的最大前缀和。
如果两区间有交，答案为以下三者中的最大值：
- $[x_2,y_1]$ 的最大子段和。
- $[x_1,x_2)$ 的最大后缀和加 $[x_2,y_2]$ 的最大前缀和。
- $[x_1,y_1]$ 的最大后缀和加 $(y_1,y_2]$ 的最大后缀和。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10;

int n,Q,a[N];

struct node { int sum,lmax,rmax,ans; };
node operator +(node a,node b) {
    node c;
    c.sum=a.sum+b.sum;
    c.lmax=max(a.lmax,a.sum+b.lmax);
    c.rmax=max(b.rmax,b.sum+a.rmax);
    c.ans=max(max(a.ans,b.ans),a.rmax+b.lmax);
    return c;
}

#define ls (o<<1)
#define rs (o<<1|1)
node t[N<<2];
inline void build(int o,int l,int r) {
    if (l==r) {
        t[o].sum=t[o].lmax=t[o].rmax=t[o].ans=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    t[o]=t[ls]+t[rs];
}
inline node query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return t[o];
    int mid=(l+r)>>1;
    if (qr<=mid) return query(ls,l,mid,ql,qr);
    else if (ql>mid) return query(rs,mid+1,r,ql,qr);
    else return query(ls,l,mid,ql,mid)+query(rs,mid+1,r,mid+1,qr);
}
#undef ls
#undef rs

inline int calc(int l1,int r1,int l2,int r2) {
    int res;
    if (r1<l2) {
        res=query(1,1,n,l1,r1).rmax;
        res+=query(1,1,n,l2,r2).lmax;
        if (r1+1<l2)res+=query(1,1,n,r1+1,l2-1).sum;
    } else {
        res=query(1,1,n,l2,r1).ans;
        res=max(res,query(1,1,n,l1,l2).rmax+query(1,1,n,l2,r2).lmax-a[l2]);
        res=max(res,query(1,1,n,l1,r1).rmax+query(1,1,n,r1,r2).lmax-a[r1]);
    }
    return res;
}

int main() {
    int T=read();
    while (T--) {
        n=read();
        for (re int i=1;i<=n;++i) a[i]=read();
        build(1,1,n);
        Q=read();
        while (Q--) {
            int l1=read(),r1=read(),l2=read(),r2=read();
            printf("%d\n",calc(l1,r1,l2,r2));
        }
    }
    return 0;
}

GSS6

在 GSS1 的基础上把线段树改成平衡树即可。

插入、删除、修改、查询就是基础的平衡树操作。

然后 pushup 和线段树有些不同，但本质是一样的。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,Q,a[N];

// fhq treap
int root,tot=0;
int ch[N][2],val[N],rnd[N],sz[N];
struct node { int sum,lmax,rmax,ans; } t[N];

inline int new_node(int w) {
    ++tot;
    sz[tot]=1,val[tot]=w,rnd[tot]=rand();
    t[tot].lmax=t[tot].rmax=max(w,0);
    t[tot].sum=t[tot].ans=w;
    return tot;
}
inline void pushup(int x) {
    int ls=ch[x][0],rs=ch[x][1];
    sz[x]=sz[ls]+sz[rs]+1;
    t[x].sum=t[ls].sum+val[x]+t[rs].sum;
    t[x].lmax=max(t[ls].lmax,t[ls].sum+val[x]+t[rs].lmax);
    t[x].rmax=max(t[rs].rmax,t[rs].sum+val[x]+t[ls].rmax);
    t[x].ans=max(max(t[ls].ans,t[rs].ans),t[ls].rmax+val[x]+t[rs].lmax);
}
inline void split(int o,int k,int& x,int& y) {
    if (!o) { x=y=0; return; }
    if (k<=sz[ch[o][0]]) y=o,split(ch[o][0],k,x,ch[o][0]);
    else x=o,split(ch[o][1],k-sz[ch[o][0]]-1,ch[o][1],y);
    pushup(o);
}
inline int merge(int A,int B) {
    if (!A||!B) return A+B;
    if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B),pushup(A); return A; }
    else { ch[B][0]=merge(A,ch[B][0]),pushup(B); return B; }
}

int main() {
    srand(19260817);
    n=read(); t[0].ans=-2e9;
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i) root=merge(root,new_node(a[i]));
    Q=read();
    while (Q--) {
        char op[2]; scanf("%s",op);
        int o,r,z;
        if (op[0]=='I') {
            int p=read(),x=read();
            split(root,p-1,o,r);
            root=merge(o,merge(new_node(x),r));
        } else if (op[0]=='D') {
            int p=read();
            split(root,p-1,o,r),split(r,1,r,z);
            root=merge(o,z);
        } else if (op[0]=='R') {
            int p=read(),x=read();
            split(root,p-1,o,r),split(r,1,r,z);
            val[r]=x,pushup(r);
            root=merge(o,merge(r,z));
        } else {
            int L=read(),R=read();
            split(root,R,r,z),split(r,L-1,o,r);
            printf("%d\n",t[r].ans);
            root=merge(o,merge(r,z));
        }
    }
    return 0;
}

GSS7

在 GSS1 的基础上加个树链剖分即可。

首先解决区间修改的问题，每个节点维护一个区间赋值标记即可。

链修改比较简单，把所有重链都改一遍即可。

需要注意的是链查询。因为合并两个区间时左右顺序对结果是有影响的，所以不能直接合并过去。

一种方法是维护一个 $L$ 和一个 $R$ ，分别代表左右两条链合并的结果，最后再把 $L,R$ 并起来。

写代码的时候要考虑清楚左右顺序问题，我因为这个 WA 了几发。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q,a[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int fa[N],dep[N],sz[N],hson[N],top[N];
int dfn[N],id[N],tim;
inline void dfs1(int u,int f) {
    fa[u]=f,dep[u]=dep[f]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
inline void dfs2(int u,int anc) {
    top[u]=anc,dfn[u]=++tim,id[tim]=u;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}

#define ls (o<<1)
#define rs (o<<1|1)
struct node {
    int sum,lmax,rmax,ans,flag,setv;
    node() { sum=lmax=rmax=ans=flag=setv=0; }
} t[N<<2];
node operator +(node a,node b) {
    node c;
    c.sum=a.sum+b.sum;
    c.lmax=max(a.lmax,a.sum+b.lmax);
    c.rmax=max(b.rmax,b.sum+a.rmax);
    c.ans=max(max(a.ans,b.ans),a.rmax+b.lmax);
    c.flag=c.setv=0;
    return c;
}
inline void update(int o,int l,int r,int w) {
    t[o].sum=(r-l+1)*w;
    t[o].lmax=t[o].rmax=t[o].ans=max(t[o].sum,0);
    t[o].flag=1,t[o].setv=w;
}
inline void pushup(int o) { t[o]=t[ls]+t[rs]; }
inline void pushdown(int o,int l,int r) {
    if (t[o].flag) {
        int mid=(l+r)>>1;
        update(ls,l,mid,t[o].setv);
        update(rs,mid+1,r,t[o].setv);
        t[o].flag=t[o].setv=0;
    }
}
inline void build(int o,int l,int r) {
    if (l==r) {
        t[o].sum=a[id[l]];
        t[o].lmax=t[o].rmax=t[o].ans=max(t[o].sum,0);
        t[o].flag=t[o].setv=0;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
inline void modify(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) { update(o,l,r,w); return; }
    int mid=(l+r)>>1; pushdown(o,l,r);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
inline node query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return t[o];
    int mid=(l+r)>>1; node res; pushdown(o,l,r);
    if (ql<=mid) res=res+query(ls,l,mid,ql,qr);
    if (qr>mid) res=res+query(rs,mid+1,r,ql,qr);
    pushup(o); return res;
}
#undef ls
#undef rs

inline void chain_modify(int u,int v,int w) {
    int tu=top[u],tv=top[v];
    while (tu!=tv) {
        if (dep[tu]<dep[tv]) swap(u,v),swap(tu,tv);
        modify(1,1,n,dfn[tu],dfn[u],w);
        u=fa[tu],tu=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    modify(1,1,n,dfn[v],dfn[u],w);
}
inline int chain_query(int u,int v) {
    node L,R; int tu=top[u],tv=top[v];
    while (tu!=tv) {
        if (dep[tu]<dep[tv]) {
            R=query(1,1,n,dfn[tv],dfn[v])+R;
            v=fa[tv],tv=top[v];
        } else {
            L=query(1,1,n,dfn[tu],dfn[u])+L;
            u=fa[tu],tu=top[u];
        }
    }
    if (dep[u]<dep[v]) R=query(1,1,n,dfn[u],dfn[v])+R;
    else L=query(1,1,n,dfn[v],dfn[u])+L;
    swap(L.lmax,L.rmax); return (L+R).ans;
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs1(1,0),dfs2(1,1),build(1,1,n);
    Q=read();
    while (Q--) {
        int op=read();
        if (op==1) {
            int u=read(),v=read();
            printf("%d\n",chain_query(u,v));
        } else {
            int u=read(),v=read(),w=read();
            chain_modify(u,v,w);
        }
    }
    return 0;
}

GSS8

感觉还是有点难。

首先这个操作显然用平衡树维护。

注意到 $k$ 很小，考虑每个节点对于每个 $k$ 都维护一个 $ans$ 。

然后因为是平衡树，所以直接把当前节点丢到左区间（或右区间）去，然后就是两个区间合并了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
#define int unsigned int

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10,K=10+10;

int n,Q;
int C[K][K];

inline void init() {
    srand(19260817);
    for (re int i=C[0][0]=1;i<=10;++i)
        for (re int j=C[i][0]=1;j<=i;++j)
            C[i][j]=C[i-1][j]+C[i-1][j-1];
}

// fhq treap
int root,tot=0;
int ch[N][2],sz[N],val[N],rnd[N];
int ans[N][K],pw[K];

inline int newnode(int w) {
    ++tot;
    sz[tot]=1,val[tot]=w,rnd[tot]=rand();
    for (re int i=0;i<=10;++i) ans[tot][i]=w;
    return tot;
}
inline void pushup(int x) {
    int ls=ch[x][0],rs=ch[x][1];
    sz[x]=sz[ls]+sz[rs]+1;
    for (re int i=pw[0]=1;i<=10;++i) pw[i]=pw[i-1]*(sz[ls]+1);
    for (re int k=0;k<=10;++k) {
        ans[x][k]=ans[ls][k]+val[x]*pw[k];
        for (re int i=0;i<=k;++i) ans[x][k]+=C[k][i]*pw[k-i]*ans[rs][i];
    }
}
inline void split(int o,int k,int& x,int& y) {
    if (!o) { x=y=0; return; }
    if (k<=sz[ch[o][0]]) y=o,split(ch[o][0],k,x,ch[o][0]);
    else x=o,split(ch[o][1],k-sz[ch[o][0]]-1,ch[o][1],y);
    pushup(o);
}
inline int merge(int A,int B) {
    if (!A||!B) return A+B;
    if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B),pushup(A); return A; }
    else { ch[B][0]=merge(A,ch[B][0]),pushup(B); return B; }
}

signed main() {
    init();
    n=read();
    for (re int i=1;i<=n;++i) root=merge(root,newnode(read()));
    Q=read();
    while (Q--) {
        char op[2]; scanf("%s",op);
        int o,r,z;
        if (op[0]=='I') {
            int p=read()+1,w=read();
            split(root,p-1,o,r);
            root=merge(merge(o,newnode(w)),r);
        } else if (op[0]=='D') {
            int p=read()+1;
            split(root,p-1,o,r),split(r,1,r,z);
            root=merge(o,z);
        } else if (op[0]=='R') {
            int p=read()+1,w=read();
            split(root,p-1,o,r),split(r,1,r,z);
            val[r]=w,pushup(r);
            root=merge(merge(o,r),z);
        } else {
            int L=read()+1,R=read()+1,k=read();
            split(root,L-1,o,r),split(r,R-L+1,r,z);
            printf("%u\n",ans[r][k]);
            root=merge(merge(o,r),z);
        }
    }
    return 0;
}

GSS1

GSS2

GSS3

GSS4

GSS5

GSS6

GSS7

GSS8

发表评论 取消回复

3 条评论

SPOJ GSS 系列简要题解

GSS1

GSS2

GSS3

GSS4

GSS5

GSS6

GSS7

GSS8

发表评论取消回复