M_sea

SPOJ GSS 系列简要题解
GSS1线段树上维护以下 $4$ 个东西:区间和区间最大前缀和区间最大后缀和区间最大子段和合并两个区间应该比较简单...
扫描右侧二维码阅读全文
06
2019/08

SPOJ GSS 系列简要题解

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 年 08 月 06 日 08 : 30 PM

3 条评论

  1. smy

    怎么这么快

    1. M_sea
      @smy

      感觉除了 GSS2 和 GSS8 都挺不要脑子的啊...

      1. smy
        @M_sea

        您好强啊qwq

发表评论