2243: [SDOI2011]染色
Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 6693 Solved: 2459
[ Submit][ Status][ Discuss]
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
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
1
2
HINT
数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。
Source
题解：树链剖分+线段树
因为要统计颜色段数，所以我们在线段树中维护三个两，区间左右端点的颜色，区间中颜色的段数，统计答案的时候注意衔接点的处理即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200003
using namespace std;
int belong[N],size[N],pos[N],deep[N],fa[N],n,m;
int point[N],next[N],v[N],val[N],tot,cnt,son[N],q[N];
int tr[N*4],cl[N*4],cr[N*4],a[N],cover[N*4],st[N],st1[N];
struct data{
int x,y,ans;
};
void add(int x,int y)
{
tot++; next[tot]=point[x]; point[x]=tot; v[tot]=y;
tot++; next[tot]=point[y]; point[y]=tot; v[tot]=x;
}
void dfs(int x,int f)
{
deep[x]=deep[f]+1; size[x]=1;
for (int i=point[x];i;i=next[i])
if (v[i]!=f) {
fa[v[i]]=x;
dfs(v[i],x);
size[x]+=size[v[i]];
if (size[son[x]]<size[v[i]]) son[x]=v[i];
}
}
void dfs1(int x,int chain)
{
belong[x]=chain; pos[x]=++cnt; q[cnt]=x; a[pos[x]]=val[x];
if (!son[x]) return;
dfs1(son[x],chain);
for (int i=point[x];i;i=next[i])
if (v[i]!=son[x]&&v[i]!=fa[x])
dfs1(v[i],v[i]);
}
void update(int now)
{
cl[now]=cl[now<<1];
cr[now]=cr[now<<1|1];
tr[now]=tr[now<<1]+tr[now<<1|1];
if (cr[now<<1]==cl[now<<1|1]) tr[now]--;
}
void build(int now,int l,int r)
{
if (l==r) {
cl[now]=cr[now]=a[l];
tr[now]=1;
return;
}
int mid=(l+r)/2;
build(now<<1,l,mid);
build(now<<1|1,mid+1,r);
update(now);
}
void pushdown(int now)
{
if (cover[now]) {
cl[now<<1]=cr[now<<1]=cover[now];
cl[now<<1|1]=cr[now<<1|1]=cover[now];
tr[now<<1]=tr[now<<1|1]=1;
cover[now<<1]=cover[now<<1|1]=cover[now];
cover[now]=0;
}
}
void qjchange(int now,int l,int r,int ll,int rr,int c)
{
if (ll<=l&&r<=rr) {
cl[now]=cr[now]=c;
tr[now]=1; cover[now]=c;
return;
}
int mid=(l+r)/2;
pushdown(now);
if (ll<=mid) qjchange(now<<1,l,mid,ll,rr,c);
if (rr>mid) qjchange(now<<1|1,mid+1,r,ll,rr,c);
update(now);
}
data query(int now,int l,int r,int ll,int rr)
{
if (ll<=l&&r<=rr) {
data t;
t.ans=tr[now]; t.x=cl[now]; t.y=cr[now];
return t;
}
pushdown(now);
int mid=(l+r)/2; data a,b; a.ans=0; b.ans=0; b.y=0;
if (ll<=mid) a=query(now<<1,l,mid,ll,rr);
if (rr>mid) b=query(now<<1|1,mid+1,r,ll,rr);
if (!a.ans) a.x=b.x,a.y=b.y;
if (a.ans&&b.ans&&a.y==b.x) a.ans+=b.ans-1;
else a.ans+=b.ans;
if (b.y) a.y=b.y;
return a;
}
void solve(int x,int y,int k)
{
while (belong[x]!=belong[y]) {
if (deep[belong[x]]<deep[belong[y]]) swap(x,y);
qjchange(1,1,n,pos[belong[x]],pos[x],k);
x=fa[belong[x]];
}
if (deep[x]>deep[y]) swap(x,y);
qjchange(1,1,n,pos[x],pos[y],k);
}
int solve1(int x,int y)
{
int top=0,top1=0; int ans=0;
while (belong[x]!=belong[y]) {
if (deep[belong[x]]<deep[belong[y]]) {
data t=query(1,1,n,pos[belong[y]],pos[y]);
ans+=t.ans; st1[++top1]=t.y; st1[++top1]=t.x;
y=fa[belong[y]];
}
else {
data t=query(1,1,n,pos[belong[x]],pos[x]);
ans+=t.ans; st[++top]=t.y; st[++top]=t.x;
x=fa[belong[x]];
}
}
if (deep[x]<deep[y]) {
data t=query(1,1,n,pos[x],pos[y]);
ans+=t.ans; st1[++top1]=t.y; st1[++top1]=t.x;
}
else {
data t=query(1,1,n,pos[y],pos[x]);
ans+=t.ans; st[++top]=t.y; st[++top]=t.x;
}
for (int i=2;i<=top;i+=2)
if (st[i]==st[i+1]&&i+1<=top) ans--;
for (int i=2;i<=top1;i+=2)
if (st1[i]==st1[i+1]&&i+1<=top1) ans--;
if (st[top]==st1[top1]&&top&&top1) ans--;
return ans;
}
int main()
{
freopen("a.in","r",stdin);
freopen("my.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&val[i]);
for (int i=1;i<n;i++){
int x,y; scanf("%d%d",&x,&y);
add(x,y);
}
dfs(1,0); dfs1(1,1);
//for (int i=1;i<=n;i++) cout<<q[i]<<" ";
//cout<<endl;
build(1,1,n); //cout<<tr[1]<<endl;
for (int i=1;i<=m;i++){
char s[10]; int x,y,k;
scanf("%s",s+1);
if (s[1]=='C') {
scanf("%d%d%d",&x,&y,&k);
solve(x,y,k);
}
else {
scanf("%d%d",&x,&y);
printf("%d\n",solve1(x,y));
}
}
}