emmmm裸的树剖，但是考点好像是在线段树上……

如何维护一个区间里有多少个连续相同的数字块呢？考虑对于\(a\)和\(b\)两个区间，如果他们相接的端点颜色相同，那么合并出的新区间的\(seg = seg[a] + seg[b] - 1\)，否则就是\(seg = seg[a] + seg[b]\)

这就是pushup操作了，但是懒标记怎么下推？直接把区间\(seg = 1\)即可，因为这一个区间颜色都一样了，但是两个端点的颜色要注意修改。

那问题到了剖分：一条路径由多条树链组成，树链首尾相连，也要考虑相接端点。

#include 
    
     #include 
     
      #include 
      
       #define MAXN 100005#define lson (rt<<1)#define rson (rt<<1|1)#define mid ((l+r)>>1)struct edge {    int v,next;}G[MAXN<<1];int head[MAXN];struct Node {    int u,from;};int val[MAXN],a[MAXN];int seg[MAXN<<2],tag[MAXN<<2];int dfn[MAXN],top[MAXN];int size[MAXN],son[MAXN],fa[MAXN],d[MAXN];int N,M,tot = 0,num = 0;inline void add(int u,int v) {    G[++tot].v = v;G[tot].next = head[u];head[u] = tot;}inline void pushup(int rt,int l,int r) {    seg[rt] = seg[lson] + seg[rson];    if(val[mid]==val[mid+1]) seg[rt]--;}void Build(int rt,int l,int r) {    tag[rt] = 0;    if(l==r) {        seg[rt] = 1;        return;    }    Build(lson,l,mid);    Build(rson,mid+1,r);    pushup(rt,l,r);}inline void pushdown(int rt,int l1,int r1,int l2,int r2) {    if(tag[rt]==0) return;    tag[lson] = tag[rson] = tag[rt];    seg[lson] = seg[rson] = 1;    val[l1] = val[r1] = val[l2] = val[r2] = tag[rt];    tag[rt] = 0;}void update(int C,int L,int R,int rt,int l,int r) {    if(L<=l&&R>=r) {        seg[rt] = 1;        tag[rt] = C;        val[l] = val[r] = C;        return;    }    if(L>r||R
       
        mid) update(C,L,R,rson,mid+1,r);    pushup(rt,l,r);}int query(int L,int R,int rt,int l,int r) {    if(L<=l&&R>=r) return seg[rt];    if(L>r||R
        
         mid) right = query(L,R,rson,mid+1,r);    pushup(rt,l,r);     int r1 = mid,l2 = mid+1;    if(left==0) return right;    else if(right==0) return left;    else if(val[r1]==val[l2]) return left+right-1;    else return left+right;   }void dfs1(int u,int father) {    d[u] = d[father] + 1;size[u] = 1;    fa[u] = father;son[u] = 0;    for(int i=head[u];i;i=G[i].next) {        int v = G[i].v;if(v==father) continue;        dfs1(v,u);        size[u] += size[v];        if(size[son[u]]
         
          d[v.u]) std::swap(u,v); ans += query(dfn[u.u],dfn[v.u],1,1,N); if(u.from!=0&&val[u.from]==val[dfn[u.u]]) ans--; if(v.from!=0&&val[v.from]==val[dfn[v.u]]) ans--; return ans; }inline void chain_update(int x,int y,int w) { while(top[x]!=top[y]) { if(d[top[x]]
          
           d[y]) std::swap(x,y); update(w,dfn[x],dfn[y],1,1,N);}int main() { int u,v; scanf("%d%d",&N,&M); for(int i=1;i<=N;++i) { scanf("%d",&a[i]); } for(int i=1;i