【BZOJ】3052: [wc2013]糖果公园树分块+带修改莫队算法

【题目】#58. 【WC2013】糖果公园

【题意】给定n个点的树，m种糖果，每个点有糖果ci。给定n个数wi和m个数vi，第i颗糖果第j次品尝的价值是v(i)*w(j)。q次询问一条链上每个点价值的和或修改一个点的糖果ci。n,m,q<=10^5。

【算法】树分块+带修改莫队算法

【题解】参考：WC 2013 糖果公园 park 题解 by vfleaking

首先树分块，参考王室联邦的方法。确定块大小为B，一遍DFS可以分成若干大小为[B,3B]的块，性质是块内两点距离至多为B。

定义(x,y,t)表示询问经过了t次修改的树链x-y的答案，将询问排序：第一关键字belong[x]，第二关键字belong[y]，第三关键字t。

对于一个询问，要考虑从上一次询问(x',y',t')转移。首先转移t，只需要记录每次修改前和修改后的数值，就可以实现修改或逆修改了。

然后是从树链x'-y'转移到树链x-y‘，这里需要异或操作（对称差）。所谓异或操作，就是如果x标记过就减去答案并消除标记，如果x没标记过就加上答案并增加标记。

具体过程可以参考vfk的公式推导，感性理解也很简单：定义t(x,y)表示除了lca(x,y)的树链x-y，那么 t(x,y') = t(x',y') ^ t(x,x') 。

有了这个，我们只要在当前基础上异或一下t(x,x')和t(y,y')就可以实现从x'-y'转移到x-y了，当然LCA全部另外算就可以了。

另外，之前修改点x的数值时，如果在当前答案中必须消除，修改，再加入。

【复杂度分析】假设块大小为B。（随便看看就好了，这部分不保证正确……）

如果u和v都不移出块，那么位置移动复杂度O(q*B)，时间移动复杂度O(q)。

如果v移出块，那么因为belong[u]只有n/B种可能，位置移动复杂度O(n*n/B)。

如果u移出块，那么位置移动的复杂度O(n)。

而belong[u],belong[v]只有(n/B)^2种可能，所以时间移动的复杂度是O(q*(n/B)^2)。

平衡后B=n^(2/3)。

所以总复杂度O(n^(5/3))。

因为树分块的块大小实际上比B大，所以取B=N^(2/3)*0.5时常数比较优秀。

有一个常数友好的优化，即使询问时如果x所在块编号比y大，那么交换，这样y的移动就会少一半的空间。至多优化一半的常数。

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

using namespace std;

int read(){

    int s=,t=;char c;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

const int maxn=;

int tot,n,m,q,B,top,cnt,c0,c1;

int first[maxn],deep[maxn],f[maxn][],belong[maxn],st[maxn],num[maxn],c[maxn],w[maxn],v[maxn],pre[maxn];

long long ans,ANS[maxn];

bool vis[maxn];

struct edge{int v,from;}e[maxn*];

struct C0{int x,y,pre;}a[maxn];

struct C1{int x,y,t,id;}b[maxn];

void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}

void dfs(int x,int fa){

    int lim=top;

    for(int j=;(<<j)<=deep[x];j++)f[x][j]=f[f[x][j-]][j-];

    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){

        deep[e[i].v]=deep[x]+;

        f[e[i].v][]=x;

        dfs(e[i].v,x);

        if(top-lim>=B){

            cnt++;

            while(top>lim)belong[st[top--]]=cnt;

        }

    }

    st[++top]=x;

}

int lca(int x,int y){

    if(deep[x]<deep[y])swap(x,y);

    int d=deep[x]-deep[y];

    for(int j=;(<<j)<=d;j++)if((<<j)&d)x=f[x][j];

    if(x==y)return x;

    for(int j=;j>=;j--)if((<<j)<=deep[x]&&f[x][j]!=f[y][j])x=f[x][j],y=f[y][j];

    return f[x][];

}

void reverse(int x){

    if(vis[x])ans-=1ll*w[num[c[x]]--]*v[c[x]];

    else ans+=1ll*w[++num[c[x]]]*v[c[x]];

    vis[x]^=;

}

void modify(int x,int y){

    if(!vis[x])c[x]=y;

    else reverse(x),c[x]=y,reverse(x);

}

void solve(int x,int y){

    while(x!=y){

        if(deep[x]>deep[y])reverse(x),x=f[x][];

        else reverse(y),y=f[y][];

    }

}

bool cmp(C1 a,C1 b){return belong[a.x]<belong[b.x]||(belong[a.x]==belong[b.x]&&belong[a.y]<belong[b.y])||

(belong[a.x]==belong[b.x]&&belong[a.y]==belong[b.y]&&a.t<b.t);}

int main(){

    n=read();m=read();q=read();

    for(int i=;i<=m;i++)v[i]=read();

    for(int i=;i<=n;i++)w[i]=read();

    for(int i=;i<n;i++){

        int u=read(),v=read();

        insert(u,v);insert(v,u);

    }

    B=pow(n,2.0/)*0.5;

    dfs(,);

    while(top)belong[st[top--]]=cnt;

    for(int i=;i<=n;i++)c[i]=pre[i]=read();

    for(int i=;i<=q;i++){

        int kind=read(),x=read(),y=read();

        if(!kind){

            a[++c0]=(C0){x,y,pre[x]},pre[x]=y;

        }

        else{

            b[++c1]=(C1){x,y,c0,c1};

            if(belong[b[c1].x]>belong[b[c1].y])swap(b[c1].x,b[c1].y);

        }

    }

    sort(b+,b+c1+,cmp);

    for(int i=;i<=b[].t;i++)modify(a[i].x,a[i].y);

    solve(b[].x,b[].y);

    int c=lca(b[].x,b[].y);

    reverse(c);ANS[b[].id]=ans;reverse(c);

    for(int i=;i<=c1;i++){

        for(int j=b[i-].t+;j<=b[i].t;j++)modify(a[j].x,a[j].y);

        for(int j=b[i-].t;j>b[i].t;j--)modify(a[j].x,a[j].pre);

        solve(b[i-].x,b[i].x);solve(b[i-].y,b[i].y);

        int c=lca(b[i].x,b[i].y);

        reverse(c);ANS[b[i].id]=ans;reverse(c);

    }

    for(int i=;i<=c1;i++)printf("%lld\n",ANS[i]);

    return ;

}

这道题主要是树上莫队和带修改莫队的结合：

1.树上莫队没有什么高论，就是把分块换成树分块，然后转移区间的时候使用(x,x')和(y,y')而已。

2.待修改莫队一个是关键字排序，另一个是对称差操作。

然后本题之所以必须考虑分块，是因为询问的信息是需要整条链的每个节点的信息，这不得不对链暴力。

巴特西

【BZOJ】3052: [wc2013]糖果公园树分块+带修改莫队算法

最新文章

热门文章

巴特西

【BZOJ】3052: [wc2013]糖果公园 树分块+带修改莫队算法

最新文章

热门文章

【BZOJ】3052: [wc2013]糖果公园树分块+带修改莫队算法