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

Source

思路

树链剖分+线段树

代码实现

1 #include
      
         2 const int maxn=1e5+10;  3 inline int min_(int x,int y){
    return x
       
        y?x:y;}  5 inline void swap_(int&x,int&y){x^=y,y^=x,x^=y;}  6 int n,m;  7 int a,b,c,ans;  8 int ss,s[maxn];  9 int h[maxn],hs,et[maxn<<1],en[maxn<<1]; 10 int t[maxn<<2],tl[maxn<<2],tr[maxn<<2],tf[maxn<<2]; 11 int ps[maxn],pd[maxn],pf[maxn],psz[maxn],pws[maxn],pp[maxn],pps,pt[maxn]; 12 void dfs1(int k,int f,int d){ 13     psz[k]=1,pf[k]=f,pd[k]=d; 14     for(int i=h[k];i;i=en[i]) 15     if(et[i]!=f){ 16         dfs1(et[i],k,d+1); 17         psz[k]+=psz[et[i]]; 18         if(psz[et[i]]>psz[pws[k]]) pws[k]=et[i]; 19     } 20 } 21 void dfs2(int k,int t){ 22     ++pps,s[pps]=ps[k],pp[k]=pps,pt[k]=t; 23     if(pws[k]) dfs2(pws[k],t); 24     for(int i=h[k];i;i=en[i]) 25     if(et[i]!=pf[k]&&et[i]!=pws[k]) 26     dfs2(et[i],et[i]); 27 } 28 void build(int k,int l,int r){ 29     if(l==r){tl[k]=tr[k]=s[++ss],t[k]++;return;} 30     int mid=l+r>>1,ls=k<<1,rs=ls|1; 31     build(ls,l,mid); 32     build(rs,mid+1,r); 33     t[k]=t[ls]+t[rs]; 34     if(tr[ls]==tl[rs]) t[k]--; 35     tl[k]=tl[ls],tr[k]=tr[rs]; 36 } 37 void down(int k){ 38     int ls=k<<1,rs=ls|1; 39     tl[ls]=tr[ls]=tl[rs]=tr[rs]=tf[ls]=tf[rs]=tf[k]; 40     t[ls]=t[rs]=1; 41     tf[k]=0; 42 } 43 void change(int k,int l,int r,int al,int ar,int v){ 44     if(l==al&&r==ar){tl[k]=tr[k]=tf[k]=v,t[k]=1;return;} 45     if(tf[k]) down(k); 46     int mid=l+r>>1,ls=k<<1,rs=ls|1; 47     if(al<=mid) change(ls,l,mid,al,min_(ar,mid),v); 48     if(ar>mid) change(rs,mid+1,r,max_(al,mid+1),ar,v); 49     t[k]=t[ls]+t[rs]; 50     if(tr[ls]==tl[rs]) t[k]--; 51     tl[k]=tl[ls],tr[k]=tr[rs]; 52 } 53 int query(int k,int l,int r,int al,int ar){ 54     if(l==al&&r==ar) return t[k]; 55     if(tf[k]) down(k); 56     int mid=l+r>>1,ls=k<<1,rs=ls|1,ret=0,nl=0,nr=0; 57     if(al<=mid) ret+=query(ls,l,mid,al,min_(ar,mid)),nl=tr[ls]; 58     if(ar>mid) ret+=query(rs,mid+1,r,max_(al,mid+1),ar),nr=tl[rs]; 59     if(nl&&nr&&nl==nr) ret--; 60     return ret; 61 } 62 int color(int k,int l,int r,int v){ 63     if(l==r) return tl[k]; 64     if(tf[k]) down(k); 65     int mid=l+r>>1,ls=k<<1,rs=ls|1; 66     if(v<=mid) return color(ls,l,mid,v); 67     else return color(rs,mid+1,r,v); 68 } 69 int main(){ 70     scanf("%d%d",&n,&m); 71     for(int i=1;i<=n;i++) scanf("%d",&ps[i]); 72     for(int i=1;i
        
         pd[b]) swap_(a,b); 91             change(1,1,n,pp[a],pp[b],c); 92         } 93         if(ch[0]=='Q'){ 94             scanf("%d%d",&a,&b),ans=0; 95             while(pt[a]!=pt[b]){ 96                 if(pd[pt[a]]
         
          pd[b]) swap_(a,b);102             ans+=query(1,1,n,pp[a],pp[b]);103             printf("%d\n",ans);104         }105     }106     return 0;107 }