【BZOJ2243】 [SDOI2011]染色

Description

給定一棵有n個節點的無根樹和m個操作，操作有2類：

1、將節點a到節點b路徑上所有點都染成顏色c；

2、詢問節點a到節點b路徑上的顏色段數量（連續相同顏色被認為是同一段），如“112221”由3段組成：“11”、“222”和“1”。

請你寫一個程序依次完成這m個操作。

Input

第一行包含2個整數n和m，分別表示節點數和操作數；

第二行包含n個正整數表示n個節點的初始顏色

下面?行每行包含兩個整數x和y，表示x和y之間有一條無向邊。

下面?行每行描述一個操作：

“C a b c”表示這是一個染色操作，把節點a到節點b路徑上所有點（包括a和b）都染成顏色c；

“Q a b”表示這是一個詢問操作，詢問節點a到節點b（包括a和b）路徑上的顏色段數量。

Output

對于每個詢問操作，輸出一行答案。

Sample Input

6 5

2 2 1 2 1 1

1 2

1 3

2 4

2 5

2 6

Q 3 5

C 2 1 1

Q 3 5

C 5 1 2

Q 3 5

Sample Output

3

1

2

HINT

數N<=10^5，操作數M<=10^5，所有的顏色C為整數且在[0, 10^9]之間。

【分析】

還是樹鏈剖分，主要是線段樹那里，要記錄最左邊的顏色和最右邊的顏色，合并的時候看看中間相接部分顏色是否相同，如果相同ans-1.

詢問的時候是要重鏈、輕邊的跳的，也是要記錄左右的顏色，判斷顏色是否相同。

代碼如下：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 100010

struct node
{
    int x,y,next;
}t[2*Maxn];int len=0;

int c[Maxn],fa[Maxn],size[Maxn],first[Maxn],dep[Maxn];
int top[Maxn],w[Maxn],son[Maxn];
int wl=0;

void ins(int x,int y)
{
    t[++len].x=x;t[len].y=y;
    t[len].next=first[x];first[x]=len;
}

struct nnode
{
    int l,r,lc,rc,cl,cr,sum,lazy;
}tr[2*Maxn];int tl=0;

void dfs1(int x,int f)
{
    dep[x]=dep[f]+1;
    size[x]=1;fa[x]=f;son[x]=0;
    for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)
    {
        dfs1(t[i].y,x);
        size[x]+=size[t[i].y];
        if(size[t[i].y]>size[son[x]]) son[x]=t[i].y;
    }
}

void dfs2(int x,int tp)
{
    top[x]=tp;w[x]=++wl;
    if(size[x]!=1) dfs2(son[x],tp);
    for(int i=first[x];i;i=t[i].next) if(t[i].y!=fa[x]&&t[i].y!=son[x])
    {
        dfs2(t[i].y,t[i].y);
    }
}

int build(int l,int r)
{
    int x=++tl;
    tr[x].l=l;tr[x].r=r;tr[x].lazy=-1;tr[x].sum=0;
    if(l!=r)
    {
        int mid=(l+r)>>1;
        tr[x].lc=build(l,mid);
        tr[x].rc=build(mid+1,r);
    }
    return x;
}

void upd(int x)
{
    if(tr[x].lazy==-1) return;
    tr[x].sum=1;tr[x].cl=tr[x].cr=tr[x].lazy;
    if(tr[x].l!=tr[x].r)
    {
        tr[tr[x].lc].lazy=tr[x].lazy;
        tr[tr[x].rc].lazy=tr[x].lazy;
    }
    tr[x].lazy=-1;
}

void change(int x,int l,int r,int y)
{
    if(tr[x].l==l&&tr[x].r==r)
    {
        tr[x].lazy=y;
        return;
    }
    upd(x);
    int mid=(tr[x].l+tr[x].r)>>1;
    if(r<=mid) change(tr[x].lc,l,r,y);
    else if(l>mid) change(tr[x].rc,l,r,y);
    else
    {
        change(tr[x].lc,l,mid,y);
        change(tr[x].rc,mid+1,r,y);
    }
    upd(tr[x].lc);upd(tr[x].rc);
    tr[x].cl=tr[tr[x].lc].cl;
    tr[x].cr=tr[tr[x].rc].cr;
    tr[x].sum=tr[tr[x].lc].sum+tr[tr[x].rc].sum;
    if(tr[tr[x].lc].cr==tr[tr[x].rc].cl) tr[x].sum--;
}

void ffind(int x,int y,int z)
{
    int f1=top[x],f2=top[y];
    while(f1!=f2)
    {
        if(dep[f1]<dep[f2]) 
        {
            swap(f1,f2);
            swap(x,y);
        }
        change(1,w[f1],w[x],z);
        x=fa[f1];
        f1=top[x];
    }
    if(dep[x]<dep[y]) swap(x,y);
    change(1,w[y],w[x],z);
}

int q1,q2,a1,a2;
int queryt(int x,int l,int r)
{
    upd(x);
    if(tr[x].l==l&&tr[x].r==r)
    {
        if(q1==tr[x].l) a1=tr[x].cl;
        if(q2==tr[x].r) a2=tr[x].cr;
        return tr[x].sum;
    }
    int mid=(tr[x].l+tr[x].r)>>1;
    if(r<=mid) return queryt(tr[x].lc,l,r);
    if(l>mid) return queryt(tr[x].rc,l,r);
    int ans=queryt(tr[x].lc,l,mid)+queryt(tr[x].rc,mid+1,r);
    if(tr[tr[x].lc].cr==tr[tr[x].rc].cl) ans--;
    return ans;
}

int query(int x,int y)
{
    int cl=-1,cr=-1,f1=top[x],f2=top[y];
    int ans=0;
    while(f1!=f2)
    {
        if(dep[f1]>=dep[f2])
        {
            q1=w[f1];q2=w[x];
            ans+=queryt(1,w[f1],w[x]);
            if(a2==cl) ans--;
            cl=a1;
            x=fa[f1];f1=top[x];
        }
        else
        {
            q1=w[f2];q2=w[y];
            ans+=queryt(1,w[f2],w[y]);
            if(a2==cr) ans--;
            cr=a1;
            y=fa[f2];f2=top[y];
        }
    }
    if(dep[x]<=dep[y])
    {
        q1=w[x];q2=w[y];
        ans+=queryt(1,w[x],w[y]);
        if(cl==a1) ans--;
        if(cr==a2) ans--;
    }
    else
    {
        q1=w[y];q2=w[x];
        ans+=queryt(1,w[y],w[x]);
        if(cr==a1) ans--;
        if(cl==a2) ans--;
    }
    return ans;
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    memset(first,0,sizeof(first));
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        ins(x,y);ins(y,x);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,n);
    for(int i=1;i<=n;i++) change(1,w[i],w[i],c[i]);
    char s[10];
    while(m--)
    {
        scanf("%s",s);
        if(s[0]=='Q')
        {
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%d\n",query(x,y));
        }
        else
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            ffind(x,y,z);
        }
    }
    return 0;
}

?

2016-05-12?16:34:01