首页 > 其他分享 >B. 染色(树链抛分)

B. 染色(树链抛分)

时间：2023-05-16 11:11:35浏览次数：40  
标签：颜色 int 染色 树链 抛分 return rid root 节点

B. 染色 - 树链剖分 - 比赛 - 衡中OI (tg.hszxoj.com)

题目描述

原题来自：SDOI 2011

给定一棵有  个节点的无根树和  个操作，操作共两类。

  1. 将节点  到节点  路径上的所有节点都染上颜色；

  2. 询问节点  到节点  路径上的颜色段数量，连续相同颜色的认为是同一段，例如 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

这道题可以用树链抛分解决

打个板子先

#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函数输入和处理

 

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

相关文章

  • python 中 pyfaidx 模块统计fasta文件每一条染色体的长度
     001、python版本和pip版本a、python版本[root@PC1pip]#python--versionPython3.11.3 b、pip版本[[email protected]]#pip--versionpip23.1.2from/usr/local/lib/python3.11/site-packages/pip(python3.11) 002、利用pip安装 pyfaidx模块......
  • hdu:How far away ？（树链剖分）
    ProblemDescriptionTherearenhousesinthevillageandsomebidirectionalroadsconnectingthem.Everydaypeolealwaysliketoasklikethis“HowfarisitifIwanttogofromhouseAtohouseB”?Usuallyithardtoanswer.Butluckilyintthisvilla......
  • 树链剖分学习笔记
    一棵树，支持：路径加单点查询一般树上链的问题使用树链剖分解决。重链剖分前置知识LCA，线段树定义重儿子：所有儿子中子树最大的儿子为重儿子重边：重儿子之间的连边重链：若干重儿子连成的链性质一棵树可以被剖成若干重链。优先遍历重儿子，所有重链的dfs序连续。重链数量不......
  • 最近公共祖先 树链剖分
    例题：洛谷P3379【模板】最近公共祖先（LCA）https://www.luogu.com.cn/problem/P3379首先是几个概念重儿子：父结点所有子树中最大的子树的根节点（只有一个或没有）轻儿子：父结点除了重儿子以外的所有子结点（没有或有很多个）重边：父结点和重儿子连的边轻边：父结点和轻儿子连的边重链：相接......
  • 从原理聊 JVM（一）：染色标记和垃圾回收算法
    1JVM运行时内存划分1.1运行时数据区域• 方法区属于共享内存区域，存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。运行时常量池，属于方法区的一部分，用于存放编译期生成的各种字面量和符号引用。JDK1.8之前，Hotspot虚拟机对方法区的实现叫做永久代，1......
  • 从原理聊JVM（一）：染色标记和垃圾回收算法
    作者：京东科技 康志兴1JVM运行时内存划分1.1运行时数据区域•方法区属于共享内存区域，存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。运行时常量池，属于方法区的一部分，用于存放编译期生成的各种字面量和符号引用。JDK1.8之前，Hotspot虚拟机对方法区......
  • 从原理聊JVM（一）：染色标记和垃圾回收算法
    作者：京东科技 康志兴1JVM运行时内存划分1.1运行时数据区域•方法区属于共享内存区域，存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。运行时常量池，属于方法区的一部分，用于存放编译期生成的各种字面量和符号引用。JDK1.8之前，Hotspot虚拟机对......
  • LightOJ 1348 Aladdin and the Return Journey （树链剖分）
    树链剖分模板题。最近一直有比赛。。好长时间没写了。明显生疏了。。找个模板题熟悉一下。代码如下：#include<iostream>#include<string.h>#include<math.h>#include<queue>#include<algorithm>#include<stdlib.h>#include<map>#include<set>#include......
  • BZOJ 2243 [SDOI2011] 染色 (树链剖分)
    题目地址：BZOJ2243普通的树链剖分，用线段树维护区间段数与最左边和最右边的颜色。然后当合并区间的时候判断一下左儿子的右端与右儿子的左端是否相同，若相同，则将和减去1.同样，在迭代求值的过程中，也要记录下上条链的最顶端的颜色。代码如下：#include<iostream>#include<strin......
  • SPOJ 375 QTREE系列-Query on a tree （树链剖分）
    题目地址：SPOJ375树链剖分第一发!果然是个貌似很高级的数据结构，其实就是把树的边从树形结构转化成了线性结构，从而可以用线段树或树状数组之类的数据结构进行快速维护。从而将时间缩到n*log(2*n).这题用的线段树维护的。代码如下：#include<iostream>#include<string.h......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99