正文
B20J_2243_[SDOI2011]染色_树链剖分+线段树
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
B20J_2243_[SDOI2011]染色_树链剖分+线段树
一下午净调这题了，争取晚上多做几道。
题意：
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），
如“112221”由3段组成：“11”、“222”和“1”。
分析：
线段树结点维护信息:区间内颜色段数t ,区间左端点颜色lco,区间右端点颜色rco,延迟标记lazy。
上传时lco[pos]=lco[lson];rco[pos]=rco[rson];t[pos]=t[lson]+t[rson];如果左区间右端点和右区间左端点颜色相同，区间段数减一;
查询时先加上区间对应的颜色段数(线段树区间合并)，然后每次找到上下端点的颜色（直接单点查找），这个跳链的时候就能找到，如果UC=DC，ans--；
注意每次标记下传的时机。
代码
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 1000010
#define M 2062145
#define lson pos<<1
#define rson pos<<1|1
int head[N],to[N<<1],nxt[N<<1],co[N],cnt,n,m,scc;
char ch[10];
int dep[N],fa[N],siz[N],son[N],top[N];
int t[M],lzy[M],idx[N],lco[M],rco[M],a[N];
inline void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
x*=f;
}
inline void add(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
inline void dfs1(int x,int y)
{
dep[x]=dep[y]+1;
fa[x]=y;
siz[x]=1;
for(int i=head[x];i;i=nxt[i])
{
if(to[i]!=y)
{
dfs1(to[i],x);
siz[x]+=siz[to[i]];
if(siz[to[i]]>siz[son[x]])
{
son[x]=to[i];
}
}
}
}
inline void dfs2(int x,int t)
{
top[x]=t;
idx[x]=++scc;
if(son[x])dfs2(son[x],t);
for(int i=head[x];i;i=nxt[i])
{
if(to[i]!=fa[x]&&to[i]!=son[x])
{
dfs2(to[i],to[i]);
}
}
}
inline void pud(int pos)
{
if(!lzy[pos])return ;
t[lson]=1;lzy[lson]=lco[lson]=rco[lson]=lzy[pos];
t[rson]=1;lzy[rson]=lco[rson]=rco[rson]=lzy[pos];
lzy[pos]=0;
}
inline void up(int l,int r,int pos,int x,int y,int c)
{
if(x<=l&&y>=r)
{
t[pos]=1;
lco[pos]=c;
rco[pos]=c;
lzy[pos]=c;
return ;
}
pud(pos);
int mid=l+r>>1;
if(x<=mid)up(l,mid,lson,x,y,c);
if(y>mid)up(mid+1,r,rson,x,y,c);
t[pos]=t[lson]+t[rson];
if(lco[rson]==rco[lson])t[pos]--;
lco[pos]=lco[lson];
rco[pos]=rco[rson];
}
inline int query(int l,int r,int pos,int x,int y)
{
pud(pos);
int re=0;
int mid=l+r>>1;
if(x<=l&&y>=r)
{
return t[pos];
}
if(y<=mid) return query(l,mid,lson,x,y);
else if(x>mid) return query(mid+1,r,rson,x,y);
else
{
re=query(l,mid,lson,x,y)+query(mid+1,r,rson,x,y);
if(lco[rson]==rco[lson])re--;
return re;
}
}
inline int col(int l,int r,int x,int pos)
{
pud(pos);
if(l==r)return lco[pos];
int mid=l+r>>1;
if(x<=mid)return col(l,mid,x,lson);
else return col(mid+1,r,x,rson);
}
int main()
{
read(n),read(m);
int x,y,z;
register int i;
for(i=1;i<=n;++i)
{
read(a[i]);
}
for(i=1;i<n;++i)
{
read(x),read(y);
add(x,y);
add(y,x);
}
dfs1(1,0);
dfs2(1,1);
for(i=1;i<=n;++i)up(1,n,1,idx[i],idx[i],a[i]);
while(m--)
{
scanf("%s",ch);
if(ch[0]=='C')
{
read(x),read(y),read(z);
while(top[x]!=top[y])
{
if(dep[top[x]]>dep[top[y]])swap(x,y);
up(1,n,1,idx[top[y]],idx[y],z);
y=fa[top[y]];
}
if(dep[x]<dep[y])swap(x,y);
up(1,n,1,idx[y],idx[x],z);
}
else
{
read(x),read(y);
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]>dep[top[y]])swap(x,y);
int DC=col(1,n,idx[top[y]],1),UC=col(1,n,idx[fa[top[y]]],1);
ans+=query(1,n,1,idx[top[y]],idx[y]);
if(UC==DC)ans--;
y=fa[top[y]];
}
if(dep[x]<dep[y])swap(x,y);
ans+=query(1,n,1,idx[y],idx[x]);
if(!ans)ans=1;
printf("%d\n",ans);
}
}
}
