关于
联系
Oi大佬们
keyboard_arrow_down
本站已运行
载入天数...载入时分秒...
Woshiluo's Notebook
Woshiluo
2018年9月29日
[SDOI2011]染色 — 树链剖分

0x01 写在之前–树链剖分

什么是树链剖分?可以吃吗?

树链剖分 – Luogu P3384 [模板] 树链剖分

在链接中的博文中,我们已经说明什么为树链剖分以及树链剖分的用处

很明显,树链剖分可以处理:

  • 两个点之间的最短路径上的操作[LCA可部分替代/LCT万能]
  • 子树之间的操作[DFN序可替代]

由于我们已经将一棵树变成了多条链,且编号是连续的,所以我们就可以转化成各种RMQ问题,然后各种东西瞎整

显然大多数情况线段树,都比较靠谱,但是如果是线段树,就不得不说到两个大头:pushuppushdown

大多数的比较毒瘤难的线段树,就在pushuppushdown上..

0x02 题目

题目链接:[https://www.luogu.org/problemnew/show/P2486]

在两个点的最短路径上操作?树剖!

但是…它求颜色怎么弄?

当然是在两个大头上弄

我们注意序号的连续和树上的连续是相同的,所以说我们可以在线段树上存三个值:

  • 左端点颜色
  • 右端点颜色
  • 总颜色段数量

然后在合并的时候考虑两个左右是否相等即可

查询时同理

0x03 代码

#include <cstdio>
using namespace std;

const int N=100010;
const int M=100010;

int n,m,u,v,x,y,z;
int col[N],ncol[N];
char op[3];

// edge start
struct edge{
    int to,next;
}e[M<<1];
int ecnt,ehead[N];
// 标准建树
inline void add_edge(int now,int to){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
// edge end
// Heavy-Light Decompostion start
// Heavy-Light Decompostion 树链剖分
// 树链剖分板子
int son[N],dep[N],mson[N],fa[N];
void dfs1(int now,int la,int depth){
    fa[now]=la;
    dep[now]=depth;
    int Max=-1;
    for(int i=ehead[now];i;i=e[i].next){
        if(e[i].to==la) continue;
        dfs1(e[i].to,now,depth+1);    
        son[now]+=son[e[i].to]+1;
        if(son[e[i].to]>Max){Max=son[e[i].to];mson[now]=e[i].to;}
    }
}

int id[N],top[N],idcnt;
void dfs2(int now,int la){
    id[now]=++idcnt;
    ncol[id[now]]=col[now];
    if(top[now]==0) top[now]=now;
    if(son[now]==0) return ;
    top[mson[now]]=top[now];
    dfs2(mson[now],now);
    for(int i=ehead[now];i;i=e[i].next){
        if(e[i].to==la||e[i].to==mson[now]) continue;
        dfs2(e[i].to,now);
    }
}
// Heavy-Light Docompostion end
// Segment Tree start
// 线段树
struct T{
    int left,rig,colnum;
}tree[N<<2];
int lazy[N<<2];
inline void pushup(int now){
    tree[now].colnum=tree[now<<1].colnum+tree[now<<1|1].colnum;
    if(tree[now<<1].rig==tree[now<<1|1].left) tree[now].colnum--;// 中间相等就一定要减一
    tree[now].rig=tree[now<<1|1].rig;tree[now].left=tree[now<<1].left;
}// 上传标记注意
inline void pushdown(int now){// 下传标记
    if(lazy[now]!=0){
        tree[now<<1].left=tree[now<<1].rig=tree[now<<1|1].left=tree[now<<1|1].rig=lazy[now];
        tree[now<<1].colnum=tree[now<<1|1].colnum=1;
        lazy[now<<1]=lazy[now<<1|1]=lazy[now];
        lazy[now]=0;
    }
}
void build_tree(int now,int left,int rig){// 建树
    if(left==rig){
        tree[now].rig=tree[now].left=ncol[left];
        tree[now].colnum=1;
        return ;
    }
    build_tree(now<<1,left,(left+rig)>>1);
    build_tree(now<<1|1,((left+rig)>>1)+1,rig);
    pushup(now);
}
void change_col(int now,int left,int rig,int from,int to,int val){
    if(from<=left&&rig<=to){// 更改颜色
        tree[now].rig=tree[now].left=val;
        tree[now].colnum=1;
        lazy[now]=val;
        return ;
    }
    pushdown(now);
    int mid=(left+rig)>>1;
    if(from<=mid) change_col(now<<1,left,mid,from,to,val);
    if(to>mid) change_col(now<<1|1,mid+1,rig,from,to,val);
    pushup(now);
}
int query_col(int now,int left,int rig,int from,int to){// 查找颜色段
    if(from<=left&&rig<=to) return tree[now].colnum;
    pushdown(now);
    int mid=(left+rig)>>1,res=0;
    if(from<=mid) res+=query_col(now<<1,left,mid,from,to);
    if(to>mid) res+=query_col(now<<1|1,mid+1,rig,from,to);
    if(from<=mid&&to>mid&&tree[now<<1].rig==tree[now<<1|1].left) res--;
    pushup(now);
    return res;
}

inline int find_col(int now,int left,int rig,int en){// 单点查找
    if(left==rig&&left==en) return tree[now].left;
    int mid=(left+rig)>>1;
    pushdown(now);
    pushup(now);
    if(en<=mid) return find_col(now<<1,left,mid,en);
    if(en>mid) return find_col(now<<1|1,mid+1,rig,en);
    return 0;
}
// Segment Tree end
// Answer start
inline void ask_change(int left,int rig,int col){// 更改
    while(top[left]!=top[rig]){
        if(dep[top[left]]<dep[top[rig]]){
            int tmp=left;
            left=rig;
            rig=tmp;
        }
        change_col(1,1,n,id[top[left]],id[left],col);// 区间修改
        left=fa[top[left]];
    }
    if(id[left]>id[rig]){
        int tmp=left;
        left=rig;
        rig=tmp;
    }
    change_col(1,1,n,id[left],id[rig],col);
}
inline int ask_colnum(int left,int rig){// 询问
    int res=0;
    while(top[left]!=top[rig]){
        if(dep[top[left]]<dep[top[rig]]){
            int tmp=left;
            left=rig;
            rig=tmp;
        }
        res+=query_col(1,1,n,id[top[left]],id[left]);
        int ta=find_col(1,1,n,id[top[left]]);
        int tb=find_col(1,1,n,id[fa[top[left]]]);// 单个颜色查找
        if(ta==tb) res--;// 相邻减一
        left=fa[top[left]];
    }
    if(id[left]>id[rig]){
        int tmp=left;
        left=rig;
        rig=tmp;
    }// 上面已经把该减的都减过了,这里就不用减掉了
    res+=query_col(1,1,n,id[left],id[rig]);
    return res;
}
// Answer end

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&col[i]);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs1(1,0,1);
    dfs2(1,0);    
    build_tree(1,1,n);
    while(m--){
        scanf("%s",op);
        if(op[0]=='C'){
            scanf("%d%d%d",&x,&y,&z);
            ask_change(x,y,z);
        }
        else if(op[0]=='Q'){
            scanf("%d%d",&x,&y);
            printf("%d\n",ask_colnum(x,y));
        }
    }
}


算竞

textsms