[WC2013]糖果公园-树上莫队

• Marvolo • 0条评论 •

寒假学习计划

题意

给出一棵树,每个节点有一个颜色.一共有m个操作,第一种操作是更改某个节点的颜色,第二种是求x到y的路径上的权值之和.权值的定义是一种颜色出现的次数乘以权重累加求和.具体见题目链接.

洛谷链接

COGS链接

题解

树上带修改莫队.

先得到欧拉序,然后再套树上莫队.和普通莫队一样,通过记录修改操作出现的时间,在移动左右端点前进行回滚或是更新操作实现颜色的修改.具体细节见代码.

最近才发现带修改莫队的分块大小应该是n^{\frac{2}{3}}而不是n^{\frac{1}{2}}.......

P.S. 不过实际测试结果显示,改成正确的大小后只比原来快了0.5s左右,效果不是很明显.

代码

树剖LCA版

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 200010
#define INF 0x3f3f3f3f
using namespace std;

int n,m,q,i,x,y,tot,block,type,cnt,lsum=1;
LL ans;
int head[N],st[N],ed[N],top[N],hson[N],last[N],fa[N],W[N],d[N],size[N];
int pos[N*2],c[N],tag[N],sum[N];
LL Ans[N],v[N],w[N];

struct Edge{
    int t,next,l;
}e[N*2];

struct Data{
    int l,r,id,lca,s;
}Q[N],cg[N];

inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline bool cmp(const Data &x,const Data &y){return (pos[x.l]==pos[y.l])?x.r<y.r:pos[x.l]<pos[y.l];}

inline LL read(){
    LL p=0; char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Add(int s,int t){
    e[lsum].t=t;    e[lsum].next=head[s];   head[s]=lsum++;
}

inline void Dfs(int x,int f){
    register int i=0,p=0;
    st[x]=++tot;    W[tot]=x;   size[x]++;
    for (i=head[x];i;i=e[i].next){
        if (f==e[i].t)  continue;
        p=e[i].t;   d[p]=d[x]+1;    fa[p]=x;
        Dfs(p,x);
        if (size[p]>size[hson[x]])  hson[x]=p;
        size[x]+=size[p];
    }
    ed[x]=++tot;    W[tot]=x;
}

inline void Cut(int x){
    register int i=0;
    top[hson[x]]=top[x];
    if (hson[x])    Cut(hson[x]);
    for (i=head[x];i;i=e[i].next){
        if (e[i].t==fa[x]||e[i].t==hson[x]) continue;
        top[e[i].t]=e[i].t; Cut(e[i].t);
    }
}

inline int LCA(int x,int y){
    while (top[x]^top[y])
        (d[top[x]]>d[top[y]])?x=fa[top[x]]:y=fa[top[y]];
    return (d[x]<d[y])?x:y;
}

inline void Update(int pos){
    if (!tag[pos]){
        sum[c[pos]]++;
        ans+=w[sum[c[pos]]]*v[c[pos]];
    }   else {
        ans-=w[sum[c[pos]]]*v[c[pos]];
        sum[c[pos]]--;
    }
    tag[pos]^=1;
}

inline void Change(int pos,int col){
    if (tag[pos]){
        Update(pos);
        c[pos]=col;
        Update(pos);
    }   else c[pos]=col;
}

inline void Solve(){
    register int r=0,l=1,i=0,j=0;
    for (i=1;i<=tot;i++){
        for (j=Q[i-1].s+1;j<=Q[i].s;j++)
            Change(cg[j].l,cg[j].r);
        for (j=Q[i-1].s;j>Q[i].s;j--)
            Change(cg[j].l,cg[j].s);
        while (r<Q[i].r)    Update(W[++r]);
        while (r>Q[i].r)    Update(W[r--]);
        while (l<Q[i].l)    Update(W[l++]);
        while (l>Q[i].l)    Update(W[--l]);
        if (Q[i].lca)   Update(Q[i].lca);
        Ans[Q[i].id]=ans;
        if (Q[i].lca)   Update(Q[i].lca);
    }
}

inline void Init(){
    register int i=0;
    for (i=1;i<=m;i++)  v[i]=read();
    for (i=1;i<=n;i++)  w[i]=read();
    for (i=1;i<n;i++){
        x=read();   y=read();
        Add(x,y);   Add(y,x);
    }
    Dfs(1,0);   top[1]=1;   Cut(1);
    block=int(sqrt(n*2));
    for (i=1;i<=2*n;i++)    pos[i]=(i-1)/block+1;
    for (i=1;i<=n;i++){
        c[i]=read();    last[i]=c[i];
    }
    tot=0;
    for (i=1;i<=q;i++){
        type=read();
        if (type){
            x=read();   y=read();
            if (st[x]>st[y])    Swap(x,y);
            ++tot;  Q[tot].id=tot;  Q[tot].s=cnt;
            if (LCA(x,y)==x)    Q[tot].l=st[x],Q[tot].r=st[y];
            else {
                Q[tot].l=ed[x]; Q[tot].r=st[y]; Q[tot].lca=LCA(x,y);
            }
        }   else {
            cg[++cnt].l=read(); cg[cnt].r=read();
            cg[cnt].s=last[cg[cnt].l];  last[cg[cnt].l]=cg[cnt].r;
        }
    }
    sort(Q+1,Q+1+tot,cmp);
}

int main(){
    n=read();   m=read();   q=read();
    Init(); Solve();
    for (i=1;i<=tot;i++)    printf("%lld\n",Ans[i]);
    return 0;
}

倍增LCA版

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 200010
#define INF 0x3f3f3f3f
using namespace std;

int n,m,q,i,x,y,tot,block,type,cnt,lsum=1;
LL ans;
int head[N],st[N],ed[N],top[N],hson[N],last[N],fa[N],W[N],d[N],size[N];
int pos[N*2],c[N],tag[N],sum[N],f[N][18],p[20];
LL Ans[N],v[N],w[N];

struct Edge{
    int t,next,l;
}e[N*2];

struct Data{
    int l,r,id,lca,s;
}Q[N],cg[N];

inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline bool cmp(const Data &x,const Data &y){return (pos[x.l]==pos[y.l])?x.r<y.r:pos[x.l]<pos[y.l];}

inline LL read(){
    LL p=0; char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Add(int s,int t){
    e[lsum].t=t;    e[lsum].next=head[s];   head[s]=lsum++;
}

inline void Dfs(int x,int fa){
    int i=0,s=0,j=0;
    st[x]=++tot;    W[tot]=x;
    for (i=head[x];i;i=e[i].next)
        if (e[i].t!=fa){
            s=e[i].t;   d[s]=d[x]+1;
            f[s][0]=x;
            for (j=1;j<=17;j++){
                if (!f[s][j-1]) break;
                f[s][j]=f[f[s][j-1]][j-1];
            }
            Dfs(s,x);
        }
    ed[x]=++tot;    W[tot]=x;
}

inline int LCA(int x,int y){
    int l=0,i=0;
    if (d[x]<d[y])  Swap(x,y);
    l=d[x]-d[y];
    for (i=0;i<=17;i++)
        if (l&p[i]) x=f[x][i];
    if (x==y)   return x;
    for (i=17;i>=0;i--)
        if (f[x][i]!=f[y][i])   x=f[x][i],y=f[y][i];
    return f[x][0];
}

inline void Update(int pos){
    if (!tag[pos]){
        sum[c[pos]]++;
        ans+=w[sum[c[pos]]]*v[c[pos]];
    }   else {
        ans-=w[sum[c[pos]]]*v[c[pos]];
        sum[c[pos]]--;
    }
    tag[pos]^=1;
}

inline void Change(int pos,int col){
    if (tag[pos]){
        Update(pos);
        c[pos]=col;
        Update(pos);
    }   else c[pos]=col;
}

inline void Solve(){
    register int r=0,l=1,i=0,j=0;
    for (i=1;i<=tot;i++){
        for (j=Q[i-1].s+1;j<=Q[i].s;j++)
            Change(cg[j].l,cg[j].r);
        for (j=Q[i-1].s;j>Q[i].s;j--)
            Change(cg[j].l,cg[j].s);
        while (r<Q[i].r)    Update(W[++r]);
        while (r>Q[i].r)    Update(W[r--]);
        while (l<Q[i].l)    Update(W[l++]);
        while (l>Q[i].l)    Update(W[--l]);
        if (Q[i].lca)   Update(Q[i].lca);
        Ans[Q[i].id]=ans;
        if (Q[i].lca)   Update(Q[i].lca);
    }
}

inline void Init(){
    register int i=0;
    for (i=1;i<=m;i++)  v[i]=read();
    for (i=1;i<=n;i++)  w[i]=read();
    for (i=1;i<n;i++){
        x=read();   y=read();
        Add(x,y);   Add(y,x);
    }
    Dfs(1,0);
    block=int(pow(n,0.5));
    for (i=1;i<=2*n;i++)    pos[i]=(i-1)/block+1;
    for (i=1;i<=n;i++){
        c[i]=read();    last[i]=c[i];
    }
    for (i=p[0]=1;i<=17;i++)    p[i]=p[i-1]<<1;
    tot=0;
    for (i=1;i<=q;i++){
        type=read();
        if (type){
            x=read();   y=read();
            if (st[x]>st[y])    Swap(x,y);
            ++tot;  Q[tot].id=tot;  Q[tot].s=cnt;
            if (LCA(x,y)==x)    Q[tot].l=st[x],Q[tot].r=st[y];
            else {
                Q[tot].l=ed[x]; Q[tot].r=st[y]; Q[tot].lca=LCA(x,y);
            }
        }   else {
            cg[++cnt].l=read(); cg[cnt].r=read();
            cg[cnt].s=last[cg[cnt].l];  last[cg[cnt].l]=cg[cnt].r;
        }
    }
    sort(Q+1,Q+1+tot,cmp);
}

inline void Write(LL x) {
    static int sta[15];
    register int top=0;
    do{
        sta[top++]=x%10,x/=10;
    }while (x);
    while (top) putchar(sta[--top]+48);
    putchar(10);
}

int main(){
    n=read();   m=read();   q=read();
    Init(); Solve();
    for (i=1;i<=tot;i++)    Write(Ans[i]);
    return 0;
}

在这道题上不知道为什树剖LCA比倍增LCA要慢一些.

声明: 本文采用 BY-NC-SA 协议进行授权，如无注明均为原创，转载请注明转自 Marvolo
本文地址: [WC2013]糖果公园-树上莫队
WC 树上莫队
说点什么
登录
支持Markdown语法
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...