B. 染色 - 树链剖分 - 比赛 - 衡中OI (tg.hszxoj.com)
题目描述
原题来自:SDOI 2011
给定一棵有 个节点的无根树和 个操作,操作共两类。
-
将节点 到节点 路径上的所有节点都染上颜色;
-
询问节点 到节点 路径上的颜色段数量,连续相同颜色的认为是同一段,例如
112221
由三段组成:11
、222
、1
。
请你写一个程序依次完成操作。
输入格式
第一行包括两个整数 ,表示节点数和操作数;
第二行包含 个正整数表示 个节点的初始颜色;
接下来若干行包含两个整数 和 ,表示 和 之间有一条无向边;
接下来若干行每行描述一个操作:
-
C a b c
表示这是一个染色操作,把节点 到节点 路径上所有点(包括 和 )染上颜色; -
Q a b
表示这是一个询问操作,把节点 到节点 路径上(包括 和 )的颜色段数量。
输出格式
对于每个询问操作,输出一行询问结果。
样例
样例输入
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
样例输出
3
1
2
数据范围与提示
对于 100% 的数据N,M<=10^5, 所有颜色 C为整数且在 [0,10^9] 之间。
用了晚三和早读时间想出来了build()和pushup和pushdown
这道题可以用树链抛分解决
打个板子先
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> #define int long long #define lid root<<1 #define rid root<<1|1 using namespace std; const int N=100005; inline int read(){ int f(1),x(0); char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48); return f*x; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } int n,m,head[N<<1],nxt[N<<1],to[N<<1],val[N],tot,num; int top[N],son[N],f[N],siz[N],in[N],rk[N]; inline void add(int x,int y){ to[++tot]=y,nxt[tot]=head[x],head[x]=tot; return ; } inline void dfs1(int now,int fa){ f[now]=fa; siz[now]=1; for(register int i=head[now];i;i=nxt[i]){ int y=to[i]; if(y==fa) continue; dfs1(y,now); siz[now]+=siz[y]; if(siz[son[now]]<siz[y]){ son[now]=y; } } } inline void dfs2(int now,int topp){ top[now]=topp; in[now]=++num; rk[num]=now; if(son[now]) { dfs2(son[now],topp); } for(register int i=head[now];i;i=nxt[i]){ int y=to[i]; if(y==f[now]||y==son[now]) continue; dfs2(y,y); } } ------------------------------------------------------------------ 树链抛分的dfs1和dfs2板子 把染的色的原来的树标明重儿子等,进行重链跑分 ------------------------------------------------------------------熟练泡粉板子捏
然后要解决这道题要明确线段树的意思
开结构体记录左右端点的颜色因为这样
当左边儿子的右端点和右边儿子的左端点重合时颜色段sum就要 - -否则就是根节点的sum=左sum+右sum
这就是pushup(根据左右儿子端点给根节点进行更新 )
红色表示线段树上左右端点的颜色
struct Retribution{ int l,r,lc,rc,sum,lazy; }t[N<<2]; inline void pushup(int root){ t[root].sum=t[lid].sum+t[rid].sum; if(t[lid].rc==t[rid].lc){ t[root].sum--; } t[root].lc=t[lid].lc; t[root].rc=t[rid].rc; }
inline void build(int root,int l,int r){ t[root].l=l,t[root].r=r; if(l==r){ t[root].lc=t[root].rc=val[rk[l]];//给左右端点颜色赋值为val[rk[l]] t[root].sum=1;//给叶子节点赋值颜色段sum为1 return ; } int mid=(l+r)>>1; build(lid,l,mid); build(rid,mid+1,r); pushup(root); }
更新
想想pushdown该怎么写?
pushdown是因为更改了根节点的值所以用结构体lazy记录未来查询或修改要给儿子们将要赋的值
先向下找到修改区间[l,r]
要把[1,2]颜色都改为4的话
把[1,2]区间的颜色段改为1 左右端点的颜色都更新为4 lazy更新为4
如果后面有操作涉及到[1,2]下面的节点的话,就把左儿子节点的左右端点颜色和右儿子节点的左右端点颜色都改成lazy(或者根节点的左右端点颜色)
最后回溯的时候用pushup更新根节点就能完成更新力!
inline void pushdown(int root){ if(!t[root].lazy) return; t[lid].lc=t[lid].rc=t[root].lc;//或者t[root].lazy t[rid].lc=t[rid].rc=t[root].rc;//或者t[root].lazy
t[lid].sum=t[rid].sum=1; t[lid].lazy=t[rid].lazy=t[root].lazy; t[root].lazy=0; }
inline void rangeupdate(int root,int l,int r,int w){ if(t[root].l>=l&&t[root].r<=r){ t[root].lc=t[root].rc=t[root].lazy=w; t[root].sum=1; return ; } pushdown(root); int mid=(t[root].l+t[root].r)>>1; if(l<=mid) rangeupdate(lid,l,r,w); if(r>mid) rangeupdate(rid,l,r,w); pushup(root); }
修改路径上的值和树链抛分板子一样捏:
inline void qchange(int x,int y,int w){ while(top[x]!=top[y]){ if(in[top[x]]<in[top[y]]){//我这里和普通板子不一样是用dfn的顺序排的其实和dep的一样 swap(x,y); } rangeupdate(1,in[top[x]],in[x],w);//更新重链顶端到当前节点的值 x=f[top[x]]; } if(in[x]>in[y]){ swap(x,y); }//在同一重链上找dfn靠前的 rangeupdate(1,in[x],in[y],w); return ; }
查询
查询和修改有些不一样
如果查询区间在同一侧就返回值
但是如果查询区间在两侧需要考虑颜色的重合
如图,如果查[1,2]直接返回[1,2]的sum
但是如果查询[2,3]你[1,2]区间的sum没有用力只能找到画黄圈的两个节点,如果根节点的左儿子のrc and 右儿子のlc 相同 查询值--;(对应图中[1,2]和[3,4]的小黄圈)
这样操作是因为叶子节点的rc一定会上传到根节点的rc,lc同理
inline int askrangecolor(int root,int l,int r){ if(l>r) swap(l,r); if(t[root].l==l&&t[root].r==r){ return t[root].sum; } pushdown(root); int mid=(t[root].l+t[root].r)>>1; if(r<=mid) return askrangecolor(lid,l,r); else if(l>mid) return askrangecolor(rid,l,r); else { int pentiment=askrangecolor(lid,l,mid)+askrangecolor(rid,mid+1,r); if(t[lid].rc==t[rid].lc) pentiment--; return pentiment; } }
求两点之间ask的完了还需要求路径上的颜色段也和板子有点不一样
如图对x到yの路径查询颜色段
如果按照板子打 能求出y所在重链的颜色段和 以及 x所在重链的颜色段和
这是两端独立的颜色段和
但是如果
存在这种情况这种求法只能找出左红圈的颜色段+右红圈的颜色段 和
所以需要一个函数asksinglecolor()来求出某个点的颜色 这是为了给求路径上的颜色段和(就是上一行所说) 减去 (如果 浅重链顶部的颜色 和 浅重链顶部的父亲节点颜色 相同就减去1)
因为叶子节点的左右端点颜色相同所以返回lc或者rc作用相同
inline int asksinglecolor(int root,int l,int r){ if(t[root].l==l&&t[root].r==r){ return t[root].lc;//返回lc和rc意思一样 } pushdown(root); int mid=(t[root].l+t[root].r)>>1; if(l<=mid) return asksinglecolor(lid,l,r);//找左区间 else return asksinglecolor(rid,l,r);//否则找右区间 }
Q:这样操作线段树明显非叶子节点的左右颜色不同啊?
A:因为是求原来的树而不是线段树 的颜色捏
接下来需要求路径(比普通的板子上多加一个判断)
inline int qsum(int x,int y){ int arcaea(0),aa(0),bb(0); while(top[x]!=top[y]){ if(in[top[x]]<in[top[y]]) { swap(x,y); } aa=asksinglecolor(1,in[top[x]],in[top[x]]);//浅重链顶部的颜色 bb=asksinglecolor(1,in[f[top[x]]],in[f[top[x]]]);//浅重链顶部的父亲节点颜色 arcaea+=askrangecolor(1,in[top[x]],in[x]); if(aa==bb) arcaea--;//如果相同就减一 避免了上图的情况出现 x=f[top[x]]; } if(in[x]>in[y]){ swap(x,y); } arcaea+=askrangecolor(1,in[x],in[y]); return arcaea; }
然后就没了捏
main函数输入和处理
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
signed main(void){ n=read(),m=read(); for(register int i=1;i<=n;i++){ val[i]=read(); } for(register int i=1;i<n;i++){ register int asd=read(),jkl=read(); add(asd,jkl),add(jkl,asd); } dfs1(1,0),dfs2(1,1),build(1,1,n); while(m--){ int x,y,z; char ch; cin>>ch; if(ch=='Q'){ x=read(),y=read(); write(qsum(x,y)),putchar('\n'); } else { x=read(),y=read(),z=read(); qchange(x,y,z); } } return 0; }View Code
最后附上AC代码
#include<bits/stdc++.h>//染色 #define int long long #define lid root<<1 #define rid root<<1|1 using namespace std; const int N=100005; inline int read(){ int f(1),x(0); char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48); return f*x; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } int n,m,head[N<<1],nxt[N<<1],to[N<<1],val[N],tot,num; int top[N],son[N],f[N],siz[N],in[N],out[N],rk[N]; inline void add(int x,int y){ to[++tot]=y,nxt[tot]=head[x],head[x]=tot; return ; } inline void dfs1(int now,int fa){ f[now]=fa; siz[now]=1; for(register int i=head[now];i;i=nxt[i]){ int y=to[i]; if(y==fa) continue; dfs1(y,now); siz[now]+=siz[y]; if(siz[son[now]]<siz[y]){ son[now]=y; } } } inline void dfs2(int now,int topp){ top[now]=topp; in[now]=++num; rk[num]=now; if(son[now]) { dfs2(son[now],topp); } for(register int i=head[now];i;i=nxt[i]){ int y=to[i]; if(y==f[now]||y==son[now]) continue; dfs2(y,y); } out[now]=num; } struct Retribution{ int l,r,lc,rc,sum,lazy; }t[N<<2]; inline void pushup(int root){ t[root].sum=t[lid].sum+t[rid].sum; if(t[lid].rc==t[rid].lc){ t[root].sum--; } t[root].lc=t[lid].lc; t[root].rc=t[rid].rc; } inline void pushdown(int root){ if(!t[root].lazy) return; t[lid].lc=t[lid].rc=t[root].lc; t[rid].lc=t[rid].rc=t[root].rc; t[lid].sum=t[rid].sum=1; t[lid].lazy=t[rid].lazy=t[root].lazy; t[root].lazy=0; } inline void build(int root,int l,int r){ t[root].l=l,t[root].r=r; if(l==r){ t[root].lc=t[root].rc=val[rk[l]]; t[root].sum=1; return ; } int mid=(l+r)>>1; build(lid,l,mid); build(rid,mid+1,r); pushup(root); } inline void rangeupdate(int root,int l,int r,int w){ if(t[root].l>=l&&t[root].r<=r){ t[root].lc=t[root].rc=t[root].lazy=w; t[root].sum=1; return ; } pushdown(root); int mid=(t[root].l+t[root].r)>>1; if(l<=mid) rangeupdate(lid,l,r,w); if(r>mid) rangeupdate(rid,l,r,w); pushup(root); } inline void qchange(int x,int y,int w){ while(top[x]!=top[y]){ if(in[top[x]]<in[top[y]]){ swap(x,y); } rangeupdate(1,in[top[x]],in[x],w); x=f[top[x]]; } if(in[x]>in[y]){ swap(x,y); } rangeupdate(1,in[x],in[y],w); return ; } inline int askrangecolor(int root,int l,int r){ if(l>r) swap(l,r); if(t[root].l==l&&t[root].r==r){ return t[root].sum; } pushdown(root); int mid=(t[root].l+t[root].r)>>1; if(r<=mid) return askrangecolor(lid,l,r); else if(l>mid) return askrangecolor(rid,l,r); else { int pentiment=askrangecolor(lid,l,mid)+askrangecolor(rid,mid+1,r); if(t[lid].rc==t[rid].lc) pentiment--; return pentiment; } } inline int asksinglecolor(int root,int l,int r){ if(t[root].l==l&&t[root].r==r){ return t[root].lc; } pushdown(root); int mid=(t[root].l+t[root].r)>>1; if(l<=mid) return asksinglecolor(lid,l,r); else return asksinglecolor(rid,l,r); } inline int qsum(int x,int y){ int arcaea(0),aa(0),bb(0); while(top[x]!=top[y]){ if(in[top[x]]<in[top[y]]) { swap(x,y); } aa=asksinglecolor(1,in[top[x]],in[top[x]]); bb=asksinglecolor(1,in[f[top[x]]],in[f[top[x]]]); arcaea+=askrangecolor(1,in[top[x]],in[x]); if(aa==bb) arcaea--; x=f[top[x]]; } if(in[x]>in[y]){ swap(x,y); } arcaea+=askrangecolor(1,in[x],in[y]); return arcaea; } signed main(void){ n=read(),m=read(); for(register int i=1;i<=n;i++){ val[i]=read(); } for(register int i=1;i<n;i++){ register int asd=read(),jkl=read(); add(asd,jkl),add(jkl,asd); } dfs1(1,0),dfs2(1,1),build(1,1,n); while(m--){ int x,y,z; char ch; cin>>ch; if(ch=='Q'){ x=read(),y=read(); write(qsum(x,y)),putchar('\n'); } else { x=read(),y=read(),z=read(); qchange(x,y,z); } } return 0; }
完结撒花
标签:颜色,int,染色,树链,抛分,return,rid,root,节点 From: https://www.cnblogs.com/phigros/p/17404112.html