【BZOJ3052】[wc2013]糖果公园

2015.08.02 16:30 Sun | 22次阅读 | 旧日oi | 固定链接 | 源码

题目大意

 给定一颗树,每个节点有一种糖果,每种糖果有一个价值,有一些操作:修改某一个节点的糖果种类;查询一段路径上的糖果价值的加权和(这个无所谓,看题就行)。

题解

嗯,当时学莫队没有做这个题,由于要互相讲课了,我要讲莫队,所以来把这个切掉……
先是常规的树分块,块的大小是n的2/3次方,为什么要分这么大呢,一会再说。
对于每个操作,如果是修改,存下修改的是哪个节点,修改前的颜色,修改后的颜色。如果是查询,存下左右端点和lca和编号(id)和前面有多少个修改操作(tim)。
对操作排序,以左端点所在块为第一关键字,右端点所在块为第二关键字,前面有多少个修改为第三关键字排序。然后按照顺序扫询问。
每扫到一个询问,首先处理时间的转移,如果i上一个操作的tim大,就把多的这部分修改应用上,如果少,就撤销掉,操作的时候要注意这个点是否在已被计算的路径中。
然后处理路径的转移,这里可以参见vfk的博客,公式看着繁琐其实很好懂。
然后这道题就处理完了。
时间复杂度?
我就来简单的分析一下。
一共有n的1/3次方个块,所以所有的询问的左右端点所在的块的取值最多之后n的2/3次方种,对于每一种,对时间的修改最多会从尾改到头,所以又多乘一个q,n,q同阶,所以总复杂度O(n^3/5),如果两个询问的两个端点分别都在同一个块内的话,复杂度就到了块内的转移里,每块的大小是n^2/3次,所以复杂度也是O(n^5/3)。强行不到O(n^2).

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define N 100005
int n,m,Q;
ll v[N],w[N],ans[N];
int block,pos[N],blonum;
int no[N],cc[N],c[N],col[N],pre[N];
int fa[N][18],dep[N];
int st[N],top;
struct node
{
    int x,y,tim,id,lca;
}q[N];
struct edge
{
    int to,next;
}e[N<<1];
int h[N],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
bool cmp(const node &a,const node &b)
{
    if(pos[a.x]==pos[b.x])
    {
        if(pos[a.y]==pos[b.y]) return a.tim<b.tim;
        return pos[a.y]<pos[b.y];
    }
    return pos[a.x]<pos[b.x];
}
int dfs(int u)
{
    int siz=0;
    for(int i=1;i<=17;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=h[u];e[i].to;i=e[i].next)
    if(e[i].to!=fa[u][0])
    {
        fa[e[i].to][0]=u;
        dep[e[i].to]=dep[u]+1;
        siz+=dfs(e[i].to);
        if(siz>=block)
        {
            blonum++;
            while(siz) pos[st[top--]]=blonum,siz--;
        }
    }
    st[++top]=u;
    return siz+1;
}
int lca(int a,int b)
{
    if(dep[a]<dep[b]) swap(a,b);
    int t=dep[a]-dep[b];
    for(int i=0;i<=17;i++)
    if(t&(1<<i)) a=fa[a][i];
    if(a==b) return a;
    for(int i=17;i>=0;i--)
    if(fa[a][i]!=fa[b][i])
    a=fa[a][i],b=fa[b][i];
    return fa[a][0];
}
int now_tim;
ll now;
int vis[N],use[N];
void reverse(int x)
{
    if(use[x])
    {
        now-=v[c[x]]*w[vis[c[x]]];
        vis[c[x]]--;use[x]=0;
    }
    else
    {
        vis[c[x]]++;use[x]=1;
        now+=v[c[x]]*w[vis[c[x]]];
    }
}
void tim_change(int x,int y)
{
    if(use[x])
    {
        reverse(x);
        c[x]=y;
        reverse(x);
    }
    else c[x]=y;
}
void tim_travel(int x)
{
    for(int i=now_tim+1;i<=x;i++) tim_change(no[i],col[i]);
    for(int i=now_tim;i>x;i--) tim_change(no[i],pre[i]);
    now_tim=x;
}
void work(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y])
    {
        reverse(x);
        x=fa[x][0];
    }
    while(x!=y)
    {
        reverse(x);reverse(y);
        x=fa[x][0];y=fa[y][0];
    }
}
int main()
{
    //freopen("3052.in", "r", stdin);
    //freopen("3052.out", "w", stdout);
    cin>>n>>m>>Q;
    for(int i=1;i<=m;i++) scanf("%lld",&v[i]);
    for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
    for(int u,v,i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        ae(u,v);ae(v,u);
    }
    for(int i=1;i<=n;i++) scanf("%d",&c[i]),cc[i]=c[i];
    block=pow(n,2.0/3.0);
    dfs(1);
    while(top) pos[st[top--]]=blonum;
    int t1=0,t2=0;
    for(int a,b,d,i=1;i<=Q;i++)
    {
        scanf("%d%d%d",&a,&b,&d);
        if(a)
        {
            t2++;
            if(pos[b]>pos[d]) swap(b,d);
            q[t2].x=b;q[t2].y=d;
            q[t2].tim=t1;q[t2].id=t2;
            q[t2].lca=lca(b,d);
        }
        else
        {
            t1++;
            no[t1]=b;pre[t1]=cc[b];
            col[t1]=cc[b]=d;
        }
    }
    sort(q+1,q+t2+1,cmp);
    tim_travel(q[1].tim);
    work(q[1].x,q[1].y);
    reverse(q[1].lca);
    ans[q[1].id]=now;
    reverse(q[1].lca);
    for(int i=2;i<=t2;i++)
    {
        tim_travel(q[i].tim);
        work(q[i].x,q[i-1].x);
        work(q[i].y,q[i-1].y);
        reverse(q[i].lca);
        ans[q[i].id]=now;
        reverse(q[i].lca);
    }
    for(int i=1;i<=t2;i++) printf("%lld\n",ans[i]);
}```