bzoj 3052: [wc2013]糖果公园（带修改的树上莫队）

time limit:200 secmemory limit:512 mb
submit:892solved:425

description

 

input

output

 

sample input

sample input

sample output

84
131
27
84

hint

 

 

source

题解：bzoj 2120 和 bzoj 3757 的结合版。

注意在排序的时候第一关键字为左端点所在的块，第二关键字为右端点所在的块，第三关键字为离当前询问最近的一次修改的时间（修改是在询问之前的）

 

#include    
#include    
#include    
#include    
#include    
#define n 100003  
#define ll long long    
using namespace std;    
int n,m,k,block,top;    
int next[n*2],v[n*2],mi[20];    
int point[n],deep[n],st[n],num[n],fa[n][20];    
int c[n],tot,sz,cnt,num1,num2;  
int belong[n],dfsn[n],vis[n],last[n];  
ll ans[n],v[n],w[n],ans1;    
struct data{    
    int x,y,id,time;    
}q[n];    
struct data1{    
    int pre,c,pos;    
}p[n];    
int read()  
{  
    int x=0,f=1;char ch=getchar();  
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}  
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}  
    return x*f;  
}  
int cmp(data a,data b)    
{    
    if (belong[a.x]==belong[b.x]&&belong[a.y]==belong[b.y])    return a.time=block)    
        {    
            ++cnt;    
            for (int j=1;j<=size;j++)    
             belong[st[top--]]=cnt;    
            size=0;  
        }    
      }    
    st[++top]=x;    
    return size+1;    
}    
int lca(int x,int y)    
{    
    if (deep[x]>i&1)  x=fa[x][i];    
    if (x==y) return x;    
    for (int i=17;i>=0;i--)    
     if (fa[x][i]!=fa[y][i])    
      x=fa[x][i],y=fa[y][i];    
    return fa[x][0];    
}    
void reserve(int x)  
{  
    if(!vis[x])  
     {  
        vis[x]=1; num[c[x]]++; ans1+=v[c[x]]*w[num[c[x]]];  
     }   
    else 
     {  
        vis[x]=0; ans1-=v[c[x]]*w[num[c[x]]]; num[c[x]]--;   
     }  
}  
void solve (int x,int y)  
{  
    while (x!=y)  
     {  
        if(deep[x]>deep[y]) {  
            reserve(x); x=fa[x][0];  
        }  
        else{  
            reserve(y); y=fa[y][0];  
        }  
     }  
}  
void change(int x,int k)  
{  
    if (vis[x])  
     {  
        reserve(x);  
        c[x]=k;  
        reserve(x);  
     }  
    else c[x]=k;  
}  
int main()    
{    
    scanf("%d%d%d",&n,&m,&k);    
    for (int i=1;i<=m;i++)  v[i]=read();    
    for (int i=1;i<=n;i++)  w[i]=read();  
    for (int i=1;idfsn[y]) swap(q[num2].x,q[num2].y);    
         }    
     }    
    sort(q+1,q+num2+1,cmp);   
    for (int i=1;i<=q[1].time;i++)  
     change(p[i].pos,p[i].c);  
    solve(q[1].x,q[1].y); 
    int t=lca(q[1].x,q[1].y); 
    reserve(t);  
    ans[q[1].id]=ans1;  
    reserve(t);  
    for (int i=2;i<=num2;i++)  
    {  
        for(int j=q[i-1].time+1;j<=q[i].time;j++)  
         change(p[j].pos,p[j].c);  
        for(int j=q[i-1].time;j>q[i].time;j--)  
         change(p[j].pos,p[j].pre);  
        solve(q[i-1].x,q[i].x);  
        solve(q[i-1].y,q[i].y);  
        int t=lca(q[i].x,q[i].y);  
        reserve(t);  
        ans[q[i].id]=ans1;  
        reserve(t);  
    }    
    for (int i=1;i<=num2;i++)  
     printf("%lld\n",ans[i]);  
}