可以说是树链剖分的模板题吧

基本思想就是先树链剖分，然后用线段树维护区间，区间的颜色种类个数，区间左端点的颜色，区间右端点的颜色

区间合并时，区间的颜色种类个数=左区间个数+右区间的个数，如果左区间的右端点的颜色等于右区间的左端点的颜色，答案还要减一

下面是代码：(用的是栈模拟递归)

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #define N 100100 8 #define M 200100 9 using namespace std; 10 11 int n,m,a,b,p; 12 int color[N],head[N],go[M],next[M]; 13 14 void build(int a,int b) 15 { 16 go[++p]=b; 17 next[p]=head[a]; 18 head[a]=p; 19 } 20 21 struct dfsdata 22 { 23 int a,i; 24 void newdata(int x,int y){a=x;i=y;} 25 }Stack[N]; 26 27 struct makedata 28 { 29 int a,i,yes; 30 void newdata(int x,int y,int z=1){a=x;i=y;yes=z;} 31 }S[N]; 32 33 int tail,f[N],size[N],max_son[N],u,v,deep[N]; 34 35 void dfs() 36 { 37 int i; 38 Stack[tail=1].newdata(1,head[1]);f[1]=0;size[1]=1;deep[1]=1; 39 while (tail) 40 { 41 i=Stack[tail].i;v=Stack[tail].a; 42 if (!i) 43 { 44 size[f[v]]+=size[v]; 45 if (size[v]>size[max_son[f[v]]]) max_son[f[v]]=v; 46 tail--; 47 continue; 48 } 49 u=go[i]; 50 Stack[tail].i=next[i]; 51 if (f[v]!=u) 52 { 53 size[u]=1; 54 f[u]=v; 55 deep[u]=deep[v]+1; 56 Stack[++tail].newdata(u,head[u]); 57 } 58 } 59 } 60 61 int L[N],l_deep[N],top[N],len,que[N]; 62 63 void make() 64 { 65 int i; 66 S[tail=1].newdata(1,head[1]);L[1]=len=1;l_deep[1]=1;top[1]=1;que[1]=1; 67 while (tail) 68 { 69 v=S[tail].a;i=S[tail].i; 70 if (!i || size[v]==1){tail--;continue;} 71 if (S[tail].yes) 72 { 73 S[tail].yes=0; 74 u=max_son[v]; 75 L[u]=++len; 76 que[len]=u; 77 l_deep[u]=l_deep[v]; 78 top[u]=top[v]; 79 S[++tail].newdata(u,head[u]); 80 continue; 81 } 82 u=go[i]; 83 S[tail].i=next[i]; 84 if (u!=f[v] && u!=max_son[v]) 85 { 86 L[u]=++len; 87 que[len]=u; 88 l_deep[u]=l_deep[v]+1; 89 top[u]=u; 90 S[++tail].newdata(u,head[u]); 91 } 92 } 93 } 94 95 //==========================SegmentTree===========================// 96 int tree[N<<2],SL[N<<2],SR[N<<2],LZ[N<<2],lazy[N<<2]; 97 98 void update(int a) 99 {100 tree[a]=tree[a<<1]+tree[(a<<1)+1];101 SL[a]=SL[a<<1];SR[a]=SR[(a<<1)+1];102 if (SR[a<<1]==SL[(a<<1)+1]) tree[a]--;103 }104 105 void BuildTree(int p,int l,int r)106 {107 if (l==r)108 {109 tree[p]=1;110 SL[p]=SR[p]=color[que[l]];111 return;112 }113 int mid=(l+r)>>1;114 BuildTree(p<<1,l,mid);115 BuildTree((p<<1)+1,mid+1,r);116 update(p);117 }118 119 void Push_down(int a)120 {121 if (!LZ[a]) return;122 LZ[a]=0;123 LZ[a<<1]=LZ[(a<<1)+1]=1;124 lazy[a<<1]=lazy[(a<<1)+1]=lazy[a];125 SL[a<<1]=SR[a<<1]=SL[(a<<1)+1]=SR[(a<<1)+1]=lazy[a];126 tree[a]=tree[a<<1]=tree[(a<<1)+1]=1;127 }128 129 void Change(int p,int l,int r,int fl,int fr,int c)130 {131 if (fl<=l&&r<=fr)132 {133 LZ[p]=1;134 lazy[p]=c;135 SL[p]=SR[p]=c;136 tree[p]=1;137 return;138 }139 Push_down(p);140 int mid=(l+r)>>1;141 if (fl<=mid) Change(p<<1,l,mid,fl,fr,c);142 if (fr>mid) Change((p<<1)+1,mid+1,r,fl,fr,c);143 update(p);144 }145 146 int Query(int p,int l,int r,int fl,int fr,int al,int &x,int ar,int &y)147 {148 if (l==fl&&r==fr)149 {150 if (LZ[p])151 {152 if (l==r)153 {154 LZ[p]=0;155 tree[p]=1;156 SL[p]=SR[p]=lazy[p];157 }158 else Push_down(p),update(p);159 }160 if (l==al) x=SL[p];161 if (r==ar) y=SR[p];162 return tree[p];163 }164 Push_down(p);165 int mid=(l+r)>>1;166 if (fr<=mid) return Query(p<<1,l,mid,fl,fr,al,x,ar,y);167 if (fl>mid) return Query((p<<1)+1,mid+1,r,fl,fr,al,x,ar,y);168 int ans=Query(p<<1,l,mid,fl,mid,al,x,ar,y)+Query((p<<1)+1,mid+1,r,mid+1,fr,al,x,ar,y);169 if (SR[p<<1]==SL[(p<<1)+1]) ans--;170 return ans;171 }172 //==========================SegmentTree===========================//173 174 void Change(int a,int b,int c)175 {176 while (top[a]!=top[b])177 {178 if (l_deep[a]
           
            L[b]) swap(a,b);193 Change(1,1,n,L[a],L[b],c);194 }195 196 void Query(int a,int b)197 {198 int ans=0,ac=-1,bc=-1,x,y;199 if (a==b)200 {201 printf("1\n");202 return;203 }204 while (top[a]!=top[b])205 {206 if (l_deep[a]
            
             L[b]) swap(a,b),swap(ac,bc);223 ans+=Query(1,1,n,L[a],L[b],L[a],x,L[b],y);224 if (x==ac) ans--;225 if (y==bc) ans--;226 printf("%d\n",ans);227 }228 229 int main()230 {231 scanf("%d%d",&n,&m);232 for (int i=1;i<=n;i++) scanf("%d",color+i);233 for (int i=1;i