[SDOI2011]染色题解
题目描述
给定一棵 n 个节点的无根树，共有 m 个操作，操作分为两种：
- 将节点 a 到节点 b 的路径上的所有点（包括 a 和 b ）都染成颜色 c 。
- 询问节点 a 到节点 b 的路径上的颜色段数量。
颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成：11、222、1。
输入格式
输入的第一行是用空格隔开的两个整数，分别代表树的节点个数 n 和操作个数 m 。
第二行有 n 个用空格隔开的整数，第 i 个整数 w_i 代表结点 i 的初始颜色。
第 3 到第 (n + 1) 行，每行两个用空格隔开的整数 u, v ，代表树上存在一条连结节点 u 和节点 v 的边。
第 (n + 2) 到第 (n + m + 1) 行，每行描述一个操作，其格式为：
每行首先有一个字符 op ，代表本次操作的类型。
- 若 op 为
C，则代表本次操作是一次染色操作，在一个空格后有三个用空格隔开的整数 a, b, c ，代表将 a 到 b 的路径上所有点都染成颜色 c 。 - 若 op 为
Q，则代表本次操作是一次查询操作，在一个空格后有两个用空格隔开的整数 a, b ，表示查询 a 到 b 路径上的颜色段数量。
输出格式
对于每次查询操作，输出一行一个整数代表答案。
样例 #1
样例输入 #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
提示
数据规模与约定
对于 100\% 的数据， 1 \leq n, m \leq 10^5 ， 1 \leq w_i, c \leq 10^9 ， 1 \leq a, b, u, v \leq n ， op 一定为 C 或 Q，保证给出的图是一棵树。
除原数据外，还存在一组不计分的 hack 数据。
思路分析
因为要进行树上路径修改和查询所以第一步进行树链剖分，方便我们进行树上操作(板子就不放了)
树剖后就比较经典了，一个区间推平一个区间查询了。
这不珂朵莉树板子吗？
这题的确可以使用珂朵莉树，我刚开始以为只能骗骗分所以写了线段树的AC代码，后面看题解没想到珂朵莉树也能AC（离谱
对比
珂朵莉树
线段树
这数据还是太仁慈了，也能理解，毕竟2011年的省选题也不可能卡得到2018年的珂朵莉树。
用珂朵莉树的话就是树剖后裸的板子了，没什么好说的，所以还是来说下线段树写法吧。
正文
难点就是快速统计区间颜色段数量，可以想到分治，将每个大区间拆分成每个小区间，然后计算出小区间后再统计求出大区间的答案，
也符合线段树的思想。所以我们先定义每个小区间的信息。
struct node{
int lc,rc,sum,lazy;
}sgm[N*4];
lc，rc代表左右端点的颜色，sum代表这个区间的颜色段数。
pushup
比较直观就是把两个区间的颜色段数量加起来，但还有个细节，如果左区间的右端点颜色与右区间的左端点颜色一样，那么就代表中间就是一个连续的颜色段，只能算作一个，但左右区间都算了一次，所以要大区间的颜色段要少一个。
void pushup(int p,int pl,int pr){
int mid=(pl+pr)>>1;
sgm[p].sum=sgm[ls(p)].sum+sgm[rs(p)].sum;
if(sgm[ls(p)].rc==sgm[rs(p)].lc) {sgm[p].sum--;}
sgm[p].lc=sgm[ls(p)].lc;
sgm[p].rc=sgm[rs(p)].rc;
}
assign(推平)
先打个lazy标记，然后令左右端点颜色一样，颜色段数为1就行了。
void assign(int p,int pl,int pr,int k){//推平
sgm[p].lazy=k;
sgm[p].sum=1;
sgm[p].lc=sgm[p].rc=k;
}
pushdown
直接分给左右儿子就行了
void pushdown(int p,int pl,int pr){
if(sgm[p].lazy){
int mid=(pl+pr)>>1;
assign(ls(p),pl,mid,sgm[p].lazy);
assign(rs(p),mid+1,pr,sgm[p].lazy);
sgm[p].lazy=0;
}
}
update
套板子就可以了，在这不需要多余操作。
void update(int p,int pl,int pr,int l,int r,int k){
if(l<=pl&&pr<=r){assign(p,pl,pr,k);return ;}
int mid=(pl+pr)>>1;
pushdown(p,pl,pr);
if(l<=mid) update(ls(p),pl,mid,l,r,k);
if(mid+1<=r) update(rs(p),mid+1,pr,l,r,k);
pushup(p,pl,pr);
}
void update_c(int x,int y,int k){
while(p[x].top!=p[y].top){
if(p[p[x].top].dep<p[p[y].top].dep) swap(x,y);
update(1,1,n,p[p[x].top].id,p[x].id,k);
x=p[p[x].top].fa;
}
if(p[x].dep<p[y].dep) swap(x,y);
update(1,1,n,p[y].id,p[x].id,k);
}
query
查询时还是有个细节要注意下，上面说过，如果左区间的右端点颜色与右区间的左端点颜色一样，那么就代表中间就是一个连续的颜色段，只能算作一个，但左右区间都算了一次，所以要大区间的颜色段要少一个。在区间累加，树上累加也要注意这个细节，在穿过轻边时候，如果链头和父亲颜色一样，那么总数是要少一个的。这里利用线段树的结构二分 O(logn) 直接获取颜色的
int get_c(int p,int pl,int pr,int k){
if(pl==k){return sgm[p].lc;}
if(pr==k){return sgm[p].rc;}
pushdown(p,pl,pr);
int mid=(pl+pr)>>1;
if(k<=mid) return get_c(ls(p),pl,mid,k);
else return get_c(rs(p),mid+1,pr,k);
}
int query(int p,int pl,int pr,int l,int r){
if(l<=pl&&pr<=r){return sgm[p].sum;}
int res=0,mid=(pl+pr)>>1;
pushdown(p,pl,pr);
if(l<=mid) {res+=query(ls(p),pl,mid,l,r);}
if(mid+1<=r) {res+=query(rs(p),mid+1,pr,l,r);}
if(l<=mid&&mid+1<=r&&sgm[ls(p)].rc==sgm[rs(p)].lc) {res--;}
return res;
}
int query_c(int x,int y){
int res=0;
while(p[x].top!=p[y].top){
if(p[p[x].top].dep<p[p[y].top].dep) swap(x,y);
res+=query(1,1,n,p[p[x].top].id,p[x].id);
if(get_c(1,1,n,p[p[x].top].id)==get_c(1,1,n,p[p[p[x].top].fa].id)) {
res--;
}
x=p[p[x].top].fa;
}
if(p[x].dep<p[y].dep) swap(x,y);
res+=query(1,1,n,p[y].id,p[x].id);
return res;
}
总时间复杂度是 O(n+m(log n)^2) 。
代码实现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=114514;
int ls(int p){return (p<<1);}
int rs(int p){return (p<<1)+1;}
int m,n,a[N],w[N];
int cnt,head[N],dfn;
struct edge{
int next,to;
}e[N*2];
void add_edge(int u,int v){
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
struct tree{
int size,top,son,dep,fa,id;
}p[N];
struct node{
int lc,rc,sum,lazy;
}sgm[N*4];
void dfs1(int u,int fa){
p[u].fa=fa;
p[u].dep=p[fa].dep+1;
p[u].size=1;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(v==fa) continue;
dfs1(v,u);
p[u].size+=p[v].size;
if(p[u].son==0||p[v].size>p[p[u].son].size){
p[u].son=v;
}
}
}
void dfs2(int u,int t){
p[u].id=++dfn;
p[u].top=t;
if(!p[u].son) return;
dfs2(p[u].son,t);
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(v==p[u].fa||v==p[u].son) continue;
dfs2(v,v);
}
}
void pushup(int p,int pl,int pr){
int mid=(pl+pr)>>1;
sgm[p].sum=sgm[ls(p)].sum+sgm[rs(p)].sum;
if(sgm[ls(p)].rc==sgm[rs(p)].lc) {sgm[p].sum--;}
sgm[p].lc=sgm[ls(p)].lc;
sgm[p].rc=sgm[rs(p)].rc;
}
void assign(int p,int pl,int pr,int k){//推平
sgm[p].lazy=k;
sgm[p].sum=1;
sgm[p].lc=sgm[p].rc=k;
}
void pushdown(int p,int pl,int pr){
if(sgm[p].lazy){
int mid=(pl+pr)>>1;
assign(ls(p),pl,mid,sgm[p].lazy);
assign(rs(p),mid+1,pr,sgm[p].lazy);
sgm[p].lazy=0;
}
}
int get_c(int p,int pl,int pr,int k){
if(pl==k){return sgm[p].lc;}
if(pr==k){return sgm[p].rc;}
pushdown(p,pl,pr);
int mid=(pl+pr)>>1;
if(k<=mid) return get_c(ls(p),pl,mid,k);
else return get_c(rs(p),mid+1,pr,k);
}
void build(int p,int pl,int pr){
if(pl==pr){
sgm[p].lc=sgm[p].rc=w[pl];
sgm[p].sum=1;
return;
}
int mid=(pl+pr)>>1;
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);
pushup(p,pl,pr);
}
int query(int p,int pl,int pr,int l,int r){
if(l<=pl&&pr<=r){return sgm[p].sum;}
int res=0,mid=(pl+pr)>>1;
pushdown(p,pl,pr);
if(l<=mid) {res+=query(ls(p),pl,mid,l,r);}
if(mid+1<=r) {res+=query(rs(p),mid+1,pr,l,r);}
if(l<=mid&&mid+1<=r&&sgm[ls(p)].rc==sgm[rs(p)].lc) {res--;}
return res;
}
void update(int p,int pl,int pr,int l,int r,int k){
if(l<=pl&&pr<=r){assign(p,pl,pr,k);return ;}
int mid=(pl+pr)>>1;
pushdown(p,pl,pr);
if(l<=mid) update(ls(p),pl,mid,l,r,k);
if(mid+1<=r) update(rs(p),mid+1,pr,l,r,k);
pushup(p,pl,pr);
}
void update_c(int x,int y,int k){
while(p[x].top!=p[y].top){
if(p[p[x].top].dep<p[p[y].top].dep) swap(x,y);
update(1,1,n,p[p[x].top].id,p[x].id,k);
x=p[p[x].top].fa;
}
if(p[x].dep<p[y].dep) swap(x,y);
update(1,1,n,p[y].id,p[x].id,k);
}
int query_c(int x,int y){
int res=0;
while(p[x].top!=p[y].top){
if(p[p[x].top].dep<p[p[y].top].dep) swap(x,y);
res+=query(1,1,n,p[p[x].top].id,p[x].id);
if(get_c(1,1,n,p[p[x].top].id)==get_c(1,1,n,p[p[p[x].top].fa].id)) {
res--;
}
x=p[p[x].top].fa;
}
if(p[x].dep<p[y].dep) swap(x,y);
res+=query(1,1,n,p[y].id,p[x].id);
return res;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n-1;i++){
int x,y;
cin>>x>>y;
add_edge(x,y);
add_edge(y,x);
}
dfs1(1,1);
dfs2(1,1);
for(int i=1;i<=n;i++){
w[p[i].id]=a[i];
}
build(1,1,n);
while(m--){
int x,y,z;
char op;
cin>>op;
if(op=='Q'){
cin>>x>>y;
cout<<query_c(x,y)<<endl;
}
else {
cin>>x>>y>>z;
update_c(x,y,z);
}
}
return 0;
}
160行，可以抽一发了
我永远喜欢珂朵莉！
