题干描述
输入描述
输出格式
对于每个询问操作，输出一行答案。
输入输出样例
输入 #1 复制
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
输出 #1 复制
3
1
2
说明/提示
题干很清楚，就是树链剖分+线段树的基本操作。但是在实现的过程中有几个点需要注意一下。
我们分类讨论一下：
第一种情况：
左区间：1231（颜色个数为4） 右区间：222（个数为1）
合并后：1231222（颜色个数为4+1=5）
这是第一种情况：没有重复。
我们再来看第二种：
左区间：1231（颜色个数为4）右区间：121（个数为3）
合并后：1231121（颜色个数为4+3-1）
这就是第二种情况了，左区间的最后一个颜色和右区间的第一个颜色重合，也就重复了，所以总数减一。
因此我们在线段树更新过程中需要维护这段区间内的最左边的颜色和最右边的颜色。如果左儿子的右端点颜色和右儿子的左端点颜色相等的话，就减一就可以了。线段树区间合并的操作。
剩下的就是树链剖分将树剖成几条链了。树链剖分的基本操作。
但是树链剖分之后的这一条链上的点并不是通过一次操作就能求出来的，而是经过好几次操作，那么这几次操作之间相邻的颜色要是重了，就出现的计数错误。所以我们在求完一次之后，我们需要查询一下这次左端点的颜色和下一次查询中右端点的颜色是否相同，如果相同，就减一。
代码如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxx=1e5+100;
struct node{
int l;
int r;
int lazy;
int lcor;
int rcor;
int num;
}p[maxx<<2];
struct edge{
int to,next;
}e[maxx<<1];
int head[maxx<<1],top[maxx],fa[maxx];
int in[maxx],son[maxx],pre[maxx];
int a[maxx],deep[maxx],size[maxx];
int n,m,tot,sign;
/*----------准备阶段---------*/
inline void init()
{
memset(son,0,sizeof(son));
memset(head,-1,sizeof(head));
tot=sign=0;
}
inline void add(int u,int v)
{
e[tot].to=v,e[tot].next=head[u],head[u]=tot++;
}
/*-----------dfs-----------*/
inline void dfs1(int u,int f)
{
fa[u]=f;
deep[u]=deep[f]+1;
size[u]=1;
for(int i=head[u];i!=-1;i=e[i].next)
{
int to=e[i].to;
if(to==f) continue;
dfs1(to,u);
size[u]+=size[to];
if(size[to]>size[son[u]]) son[u]=to;
}
}
inline void dfs2(int u,int Top)
{
in[u]=++sign;
pre[sign]=u;
top[u]=Top;
if(son[u]) dfs2(son[u],Top);
for(int i=head[u];i!=-1;i=e[i].next)
{
int to=e[i].to;
if(to==fa[u]||to==son[u]) continue;
dfs2(to,to);
}
}
/*-----------线段树------------*/
inline void pushup(int cur)//往上更新的时候只传左端点颜色和右端点颜色就行
{
p[cur].lcor=p[cur<<1].lcor;
p[cur].rcor=p[cur<<1|1].rcor;
p[cur].num=p[cur<<1].num+p[cur<<1|1].num;
if(p[cur<<1].rcor==p[cur<<1|1].lcor) p[cur].num--;
}
inline void pushdown(int cur)
{
if(p[cur].lazy!=-1)
{
p[cur<<1].lazy=p[cur<<1|1].lazy=p[cur].lazy;
p[cur<<1].lcor=p[cur<<1].rcor=p[cur<<1|1].lcor=p[cur<<1|1].rcor=p[cur].lcor;
p[cur<<1].num=p[cur<<1|1].num=1;
p[cur].lazy=-1;
}
}
inline void build(int l,int r,int cur)
{
p[cur].l=l;
p[cur].r=r;
p[cur].num=0;
p[cur].lazy=-1;
p[cur].lcor=p[cur].rcor=-1;
if(l==r)
{
p[cur].lcor=p[cur].rcor=a[pre[l]];
p[cur].num=1;
return ;
}
int mid=l+r>>1;
build(l,mid,cur<<1);
build(mid+1,r,cur<<1|1);
pushup(cur);
}
inline void update(int l,int r,int cur,int col)
{
int L=p[cur].l;
int R=p[cur].r;
if(l<=L&&R<=r)
{
p[cur].lcor=p[cur].rcor=col;
p[cur].num=1;
p[cur].lazy=col;
return ;
}
pushdown(cur);
int mid=L+R>>1;
if(r<=mid) update(l,r,cur<<1,col);
else if(l>mid) update(l,r,cur<<1|1,col);
else update(l,mid,cur<<1,col),update(mid+1,r,cur<<1|1,col);
pushup(cur);
}
inline node query(int l,int r,int cur)
{
int L=p[cur].l;
int R=p[cur].r;
if(l<=L&&R<=r) return p[cur];
pushdown(cur);
int mid=L+R>>1;
if(r<=mid) return query(l,r,cur<<1);
else if(l>mid) return query(l,r,cur<<1|1);
else//区间合并，判断相邻两端点是否颜色相同
{
node a=query(l,mid,cur<<1);
node b=query(mid+1,r,cur<<1|1);
node c;
c.lcor=a.lcor;c.rcor=b.rcor;
c.num=a.num+b.num;
if(a.rcor==b.lcor) c.num--;
return c;
}
}
inline int query_col(int pos,int cur)//查询单点颜色
{
int L=p[cur].l;
int R=p[cur].r;
if(L==R) return p[cur].lcor;
pushdown(cur);
int mid=L+R>>1;
if(pos<=mid) return query_col(pos,cur<<1);
else return query_col(pos,cur<<1|1);
}
/*-------------树链剖分-------------*/
inline void Update(int x,int y,int col)
{
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
update(in[top[x]],in[x],1,col);
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
update(in[x],in[y],1,col);
}
inline int Query(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans+=query(in[top[x]],in[x],1).num;
int scol=query_col(in[top[x]],1);
int fcol=query_col(in[fa[top[x]]],1);//标记相邻端点颜色是否相同，如果相同，就减一。
if(scol==fcol) ans--;
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
ans+=query(in[x],in[y],1).num;
return ans;
}
int main()
{
int x,y,z;char c[2];
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
deep[0]=0;
dfs1(1,0);
dfs2(1,1);
build(1,n,1);
while(m--)
{
scanf("%s",c);
if(c[0]=='Q') scanf("%d%d",&x,&y),printf("%d\n",Query(x,y));
else
{
scanf("%d%d%d",&x,&y,&z);
Update(x,y,z);
}
}
return 0;
}
简化到线段版本，就简单多了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxx=5e5+100;
struct node{
int l;
int r;
int lcol;
int rcol;
int num;
int lazy;
}p[maxx<<2];
int n,m;
inline void pushdown(int cur)
{
if(p[cur].lazy!=-1)
{
p[cur<<1].lcol=p[cur<<1|1].lcol=p[cur<<1].rcol=p[cur<<1|1].rcol=p[cur].lazy;
p[cur<<1].num=p[cur<<1|1].num=1;
p[cur<<1].lazy=p[cur<<1|1].lazy=p[cur].lazy;
p[cur].lazy=-1;
}
}
inline void pushup(int cur)
{
p[cur].lcol=p[cur<<1].lcol;p[cur].rcol=p[cur<<1|1].rcol;
p[cur].num=p[cur<<1].num+p[cur<<1|1].num;
if(p[cur<<1].rcol==p[cur<<1|1].lcol) p[cur].num--;
}
inline void build(int l,int r,int cur)
{
p[cur].l=l;
p[cur].r=r;
p[cur].num=0;p[cur].lazy=-1;
if(l==r)
{
scanf("%d",&p[cur].lcol);
p[cur].rcol=p[cur].lcol;
p[cur].num=1;
return ;
}
int mid=l+r>>1;
build(l,mid,cur<<1);
build(mid+1,r,cur<<1|1);
pushup(cur);
}
inline void update(int l,int r,int cur,int col)
{
int L=p[cur].l;
int R=p[cur].r;
if(l<=L&&R<=r)
{
p[cur].lcol=p[cur].rcol=col;
p[cur].num=1;
p[cur].lazy=col;
return ;
}
pushdown(cur);
int mid=L+R>>1;
if(r<=mid) update(l,r,cur<<1,col);
else if(l>mid) update(l,r,cur<<1|1,col);
else update(l,mid,cur<<1,col),update(mid+1,r,cur<<1|1,col);
pushup(cur);
}
inline node query(int l,int r,int cur)
{
int L=p[cur].l;
int R=p[cur].r;
if(l<=L&&R<=r) return p[cur];
pushdown(cur);
int mid=L+R>>1;
if(r<=mid) return query(l,r,cur<<1);
else if(l>mid) return query(l,r,cur<<1|1);
else
{
node c;
node a=query(l,mid,cur<<1);
node b=query(mid+1,r,cur<<1|1);
if(a.rcol==b.lcol) c.num=a.num+b.num-1;
else c.num=a.num+b.num;
c.lcol=a.lcol;
c.rcol=b.rcol;
return c;
}
}
int main()
{
int op,x,y,c;
while(~scanf("%d%d",&n,&m))
{
build(1,n,1);
while(m--)
{
scanf("%d",&op);
if(op==1) scanf("%d%d%d",&x,&y,&c),update(x,y,1,c);
else
{
scanf("%d%d",&x,&y);if(x>y) swap(x,y);
printf("%d\n",query(x,y,1).num);
}
}
}
return 0;
}
努力加油a啊，(o)/~