SPOJ GSS 系列简要题解

博主： M_sea
发布时间：2019 年 08 月 06 日
4340次浏览
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 公约数
浏览次数: 38682
HNOI2019 ～Zero～
浏览次数: 28694
～After OI～
浏览次数: 19516
APIO2020 ～Intermezzo～
浏览次数: 17413
CSP2019 ～Idle Dream～
浏览次数: 12174

memset0
可爱！
草莓奶昔
一直在研究这道题，难得有这么好的码风，感谢楼主!!!
konjacq
巨佬M_sea的AFO就是去搞ACM吗orz
xgzc
现在已经拿到满意的成绩了
Qihoo360
orz

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;
}

SPOJ GSS 系列简要题解

GSS1

GSS2

GSS3

GSS4

GSS5

GSS6

GSS7

GSS8

发表评论取消回复

3 条评论

洛谷5176 公约数

HNOI2019 ～Zero～

～After OI～

APIO2020 ～Intermezzo～

CSP2019 ～Idle Dream～

LOJ2863 「IOI2018」组合动作

UVA10559 Blocks

LOJ6252 「CodePlus 2017 11 月赛」大吉大利，晚上吃鸡！

AGC027F Grafting

CSP2019 前的做题记录 III

SPOJ GSS 系列简要题解

GSS1

GSS2

GSS3

GSS4

GSS5

GSS6

GSS7

GSS8

GSS1

GSS2

GSS3

GSS4

GSS5

GSS6

GSS7

GSS8

发表评论 取消回复

3 条评论

SPOJ GSS 系列简要题解

GSS1

GSS2

GSS3

GSS4

GSS5

GSS6

GSS7

GSS8

发表评论取消回复