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
首先用树剖和线段树处理
这时线段树记录的信息有a[x].l表示这段区间最左边的颜色编号，a[x].r表示这段区间最右边的颜色编号，a[x].s表示颜色数
在push up的时候，a[x].s=a[ls].s+a[rs].s,如果a[ls].r==a[rs].l就说明重复计入了一个，那么就要讲a[x].s--;
在查询答案时也要注意这一点，对于分别查询的两个区间之间要进行颜色是否相同的判断，对于链与链之间也要进行相同的判断。
#include#include #define ls x<<1#define rs x<<1|1using namespace std;const int N=1e5+5;struct Y{ int v,f,n;}y[N<<1];struct A{ int l,r,s,lz; void fz(int g) { l=r=lz=g; s=1; }}a[N<<2];int s,ss,siz[N],fa[N],co[N],dfn[N],tou[N],hson[N],n;void add(int u,int v){ y[++s].v=v; y[s].n=y[u].f; y[u].f=s;}void dfs1(int u){ siz[u]=1; for(int i=y[u].f;i;i=y[i].n) if(y[i].v!=fa[u]) { fa[y[i].v]=u; dfs1(y[i].v); siz[u]+=siz[y[i].v]; if(siz[y[i].v]>siz[hson[u]]) hson[u]=y[i].v; }}void dfs2(int u,int to){ dfn[u]=++ss; tou[u]=to; if(hson[u]) dfs2(hson[u],to); for(int i=y[u].f;i;i=y[i].n) if(y[i].v!=hson[u]&&y[i].v!=fa[u]) dfs2(y[i].v,y[i].v);}void pd(int x,int l,int r,int mid){ if(a[x].lz) { a[ls].fz(a[x].lz),a[rs].fz(a[x].lz); a[x].lz=0; }}void chan(int x,int l,int r,int ql,int qr,int z){ if(ql<=l&&r<=qr) a[x].fz(z); else { int mid=(l+r)>>1; pd(x,l,r,mid); if(ql<=mid) chan(ls,l,mid,ql,qr,z); if(qr>mid) chan(rs,mid+1,r,ql,qr,z); a[x].l=a[ls].l;a[x].r=a[rs].r; a[x].s=a[ls].s+a[rs].s; if(a[ls].r==a[rs].l) --a[x].s; }}int askk(int x,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr) return a[x].s; int mid=(l+r)>>1,re=0; pd(x,l,r,mid); if(ql<=mid) re+=askk(ls,l,mid,ql,qr); if(qr>mid) re+=askk(rs,mid+1,r,ql,qr); if(ql<=mid&&qr>mid&&a[ls].r==a[rs].l) --re; return re;}int gc(int x,int l,int r,int wz){ if(l==r) return a[x].lz; int mid=(l+r)>>1; pd(x,l,r,mid); if(wz<=mid) return gc(ls,l,mid,wz); else return gc(rs,mid+1,r,wz);}int qu(int u,int v){ int re=0; while(tou[u]!=tou[v]) { if(dfn[u]