2243: [SDOI2011]染色
Description
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“
请你写一个程序依次完成这m个操作。
Input
第一行包含2个整数n和m，分别表示节点数和操作数；
第二行包含n个正整数表示n个节点的初始颜色
下面
下面
“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]之间。
树链剖分+线段树
这是一道提高代码能力的好题。。。。。。
#include<cstdio>
#include<iostream>
using namespace std;
int N,M,tot,L,R,Color;
int color[100001];
int first[100001];
int next[200001];
int end[200001];
int size[100001];
int fa[100001];
int son[100001];
int top[100001];
int dep[100001];
int w[100001];
int y[100001];
struct line{
int l,r,sum,tage;
}P[500001];
struct section{
int l,r,sum;
section(int x=-1,int y=-1,int z=0){
l=x; r=y; sum=z;
}
};
void Add(int x,int y){
next[++tot]=first[x]; first[x]=tot; end[tot]=y;
next[++tot]=first[y]; first[y]=tot; end[tot]=x;
}
void Dfs1(int u,int f){
fa[u]=f;
size[u]=1;
dep[u]=dep[f]+1;
for (int k=first[u],v;v=end[k],k;k=next[k])
if (v!=f){
Dfs1(v,u);
size[u]+=size[v];
if (size[son[u]]<size[v])
son[u]=v;
}
}
void Dfs2(int u,int fa){
if (son[u]){
int v=son[u];
w[v]=++tot;
y[tot]=v;
top[v]=top[u];
Dfs2(v,u);
}
for (int k=first[u],v;v=end[k],k;k=next[k]){
if (v==fa) continue;
if (v==son[u]) continue;
w[v]=++tot;
y[tot]=v;
top[v]=v;
Dfs2(v,u);
}
}
void Down(int k){
if (P[k].tage<0) return;
P[k*2].sum=P[k*2+1].sum=1;
P[k*2].tage=P[k*2+1].tage=P[k].tage;
P[k*2].l=P[k*2].r=P[k].tage;
P[k*2+1].l=P[k*2+1].r=P[k].tage;
P[k].tage=-1;
}
void Up(int k){
P[k].sum=P[k*2].sum+P[k*2+1].sum;
if (P[k*2].r==P[k*2+1].l)
P[k].sum--;
P[k].l=P[k*2].l;
P[k].r=P[k*2+1].r;
}
void BuildTree(int k,int l,int r){
P[k].tage=-1;
if (l==r){
P[k].l=P[k].r=color[y[l]];
P[k].sum=1;
return;
}
int mid=(l+r)/2;
BuildTree(k*2,l,mid);
BuildTree(k*2+1,mid+1,r);
Up(k);
}
void ChangeTree(int k,int l,int r){
if (L>r||l>R) return;
if (L<=l&&r<=R){
P[k].sum=1;
P[k].l=P[k].r=Color;
P[k].tage=Color;
return;
}
Down(k);
int mid=(l+r)/2;
ChangeTree(k*2,l,mid);
ChangeTree(k*2+1,mid+1,r);
Up(k);
}
section FindTree(int k,int l,int r){
section s;
if (L>r||l>R) return s;
if (L<=l&&r<=R){
s.l=P[k].l;
s.r=P[k].r;
s.sum=P[k].sum;
return s;
}
Down(k);
int mid=(l+r)/2;
section le=FindTree(k*2,l,mid);
section ri=FindTree(k*2+1,mid+1,r);
Up(k);
if (!le.sum) return ri;
if (!ri.sum) return le;
s.l=le.l;
s.r=ri.r;
s.sum=le.sum+ri.sum;
if (le.r==ri.l)
--s.sum;
return s;
}
void Change(int x,int y){
if (top[x]==top[y]){
if (dep[x]>dep[y])
swap(x,y);
L=w[x];
R=w[y];
ChangeTree(1,1,N);
return;
}
if (dep[top[x]]<dep[top[y]]) swap(x,y);
L=w[top[x]]; R=w[x];
ChangeTree(1,1,N);
Change(fa[top[x]],y);
}
section Find(int x,int y){
int fswap=0;
if (top[x]==top[y]){
if (dep[x]>dep[y]){
swap(x,y);
fswap=1;
}
L=w[x];
R=w[y];
section s=FindTree(1,1,N);
if (fswap) swap(s.l,s.r);
return s;
}
if (dep[top[x]]<dep[top[y]]){
swap(x,y);
fswap=1;
}
L=w[top[x]]; R=w[x];
section a=FindTree(1,1,N);
section b=Find(y,fa[top[x]]);
section s=section(a.r,b.l,a.sum+b.sum);
if (a.l==b.r) --s.sum;
if (fswap) swap(s.l,s.r);
return s;
}
int main(){
scanf("%d%d",&N,&M);
for (int i=1;i<=N;++i)
scanf("%d",&color[i]);
for (int i=1;i<N;++i){
int x,y;
scanf("%d%d",&x,&y);
Add(x,y);
}
Dfs1(1,0);
top[1]=1;
w[1]=1;
y[1]=1;
tot=1;
Dfs2(1,0);
BuildTree(1,1,N);
for (;M--;){
char s[2];
scanf("%s",s);
int x,y;
scanf("%d%d",&x,&y);
if (s[0]=='C') {
scanf("%d",&Color);
Change(x,y);
}
else {
section A=Find(x,y);
printf("%d\n",A.sum);
}
}
}
评论 (0)
