题目链接：

Time Limit: 20 Sec  Memory Limit: 512 MB

Submit: 6267  Solved: 2291

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]之间。

 

题意：

 

思路：

 

树链剖分的入门题？反正上次写hdu边那个一个T,今天写这个点的版本的还好;调了一会就过了;

 

AC代码：

#include 
      
       using namespace std;typedef long long LL;#define lson o<<1#define rson o<<1|1const int maxn=1e5+10;int n,m,a[maxn];int siz[maxn],dep[maxn],fa[maxn],son[maxn],top[maxn],tid[maxn],Rank[maxn],tim=0;vector
       
        ve[maxn];void dfs1(int cur,int father,int deep){    fa[cur]=father;    siz[cur]=1;    dep[cur]=deep;    int len=ve[cur].size();    for(int i=0;i
        
         siz[son[cur]])son[cur]=x;    }}void dfs2(int cur,int tp){    top[cur]=tp;    tid[cur]=++tim;    Rank[tim]=cur;    if(son[cur]==-1)return ;    dfs2(son[cur],tp);    int len=ve[cur].size();    for(int i=0;i
         
          =0)    {        tr[lson].sum=tr[rson].sum=1;        tr[lson].lc=tr[lson].rc=tr[o].mark;        tr[rson].lc=tr[rson].rc=tr[o].mark;        tr[lson].mark=tr[rson].mark=tr[o].mark;        tr[o].mark=-1;    }}void build(int o,int L,int R){    tr[o].l=L;tr[o].r=R;    tr[o].mark=-1;    if(L>=R)    {        tr[o].sum=1;        tr[o].lc=tr[o].rc=a[Rank[L]];        return ;    }    int mid=(L+R)>>1;    build(lson,L,mid);    build(rson,mid+1,R);    pushup(o);}void update(int o,int L,int R,int num){    if(L<=tr[o].l&&R>=tr[o].r)    {        tr[o].sum=1;        tr[o].lc=tr[o].rc=num;        tr[o].mark=num;        return ;    }    int mid=(tr[o].l+tr[o].r)>>1;    pushdown(o);    if(L<=mid)update(lson,L,R,num);    if(R>mid)update(rson,L,R,num);    pushup(o);}int query(int o,int L,int R,int & Lc,int & Rc){    if(L<=tr[o].l&&R>=tr[o].r)    {        if(L==tr[o].l)Lc=tr[o].lc;        if(R==tr[o].r)Rc=tr[o].rc;        return tr[o].sum;    }    int mid=(tr[o].l+tr[o].r)>>1;    pushdown(o);    if(R<=mid)return query(lson,L,R,Lc,Rc);    else if(L>mid)return query(rson,L,R,Lc,Rc);    else     {        int ans=query(lson,L,R,Lc,Rc)+query(rson,L,R,Lc,Rc);        if(tr[lson].rc==tr[rson].lc)ans--;        return ans;    }}void change(int u,int v,int w){    int fu=top[u],fv=top[v];        while(fu!=fv)    {        if(dep[fu]
          
           dep[fv])        {            ans+=query(1,tid[fu],tid[u],nowul,nowur);            if(nowur==preul&&preul!=-1)ans--;            preul=nowul;preur=nowur;            u=fa[fu];            fu=top[u];        }        else         {            ans+=query(1,tid[fv],tid[v],nowvl,nowvr);            if(nowvr==prevl&&prevl!=-1)ans--;            prevl=nowvl;prevr=nowvr;            v=fa[fv];            fv=top[v];        }    }        if(dep[u]>dep[v])        {            ans+=query(1,tid[v],tid[u],nowul,nowur);            if(nowur==preul&&preul!=-1)ans--;            if(nowul==prevl&&prevl!=-1)ans--;        }        else         {            ans+=query(1,tid[u],tid[v],nowvl,nowvr);            if(nowvr==prevl&&prevl!=-1)ans--;            if(nowvl==preul&&preul!=-1)ans--;        }    return ans;}int main(){    int u,v,w;    char s[5];    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)scanf("%d",&a[i]);    for(int i=1;i