[置顶] 【整合】树链剖分模板（线段树维护）

原题是SDOI2011染色
反正链剖都长得差不多不1样的就是线段树根据题自己在查询和修改里改1改就行了
随着黄学长学的倍增记录先人的写法，和网上不太1样求不喷
注释棒棒哒

代码又长跑的也不快我也是醉了

注释代码根据题目不同自己修改

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define MAXINT 0x7fffffff

#define MAXN 100010

#define lchild rt<<1,l,mid

#define rchild rt<<1|1,mid+1,r

#define ln rt<<1

#define rn rt<<1|1

using namespace std;

int n,m;

int top,tp;

int co[MAXN];

int a,b,color;

int deep[MAXN],size[MAXN],chain[MAXN],fa[MAXN][18],num[MAXN];

//deep 深度,size 子树大小,chain 接的链,fa 父亲节点,num 点的编号 

bool vis[MAXN];//节点是不是已访问过 

char ch[2];

struct seg

{

    int mark;//染色标记 

    int l,r;//对应左右区间 

    int data;//色彩段数量 

    int lc,rc;//区间左右端点色彩 

}tree[MAXN*4];

struct edge

{

    int to;

    edge *next;

}e[MAXN*2],*prev[MAXN];

void insert(int u,int v)

{

    e[++top].to=v;

    e[top].next=prev[u];

    prev[u]=&e[top];

}

void dfs1(int x)//第1遍DFS处理子树大小/先人关系/深度 

{

    size[x]=1;

    vis[x]=1;

    for (int i=1;i<=17;i++)

    {

        if (deep[x]<(1<<i)) break;

        fa[x][i]=fa[fa[x][i-1]][i-1];//倍增处理先人 

    }

    for (edge *i=prev[x];i;i=i->next)

    {

        int t=i->to;

        if (vis[t]) continue;

        deep[t]=deep[x]+1;

        fa[t][0]=x;

        dfs1(t);

        size[x]+=size[t];

    }

}

void dfs2(int x,int last)//接链上编号.last为之前的链 

{

    num[x]=++tp;

    chain[x]=last;//x为当前重子节点 

    int t=0;

    for (edge *i=prev[x];i;i=i->next)

        if (deep[i->to]>deep[x]&&size[t]<size[i->to])//寻觅重子节点 

            t=i->to;

    if (!t) return;

    dfs2(t,last);

    for (edge *i=prev[x];i;i=i->next)

        if (deep[i->to]>deep[x]&&i->to!=t)

            dfs2(i->to,i->to);//在轻子节点上重新接出新的链 

}

/*void push_up(int rt)

{

    tree[rt].lc=tree[ln].lc;tree[rt].rc=tree[rn].rc;

    tree[rt].data=tree[ln].data+tree[rn].data;

    if (tree[ln].rc==tree[rn].lc) tree[rt].data--;//左右区间相接处

    //色彩相同的话需要把data减1

}*/

/*void push_down(int rt)

{

    if (tree[rt].mark==-MAXINT) return;

    if (tree[rt].l==tree[rt].r) return;

    tree[ln].data=tree[rn].data=1;

    tree[ln].mark=tree[rn].mark=tree[ln].lc=tree[rn].lc=tree[ln].rc=tree[rn].rc=tree[rt].mark;

    tree[rt].mark=-MAXINT;

}*/

void build(int rt=1,int l=1,int r=n)

{

    /*tree[rt].l=l;

    tree[rt].r=r;

    tree[rt].data=1;

    tree[rt].mark=-MAXINT;*/

    if (l==r) return;

    int mid=(l+r)>>1;

    build(lchild);

    build(rchild);

    //push_up(rt);

}

int lca(int a,int b)//最近公共先人.将链提到最近公共先人上 

{

    if (deep[a]<deep[b]) swap(a,b);

    int t=deep[a]-deep[b];

    for (int i=0;i<=17;i++)

        if (t&(1<<i)) a=fa[a][i];

    for (int i=17;i>=0;i--)

        if (fa[a][i]!=fa[b][i])

        {

            a=fa[a][i];

            b=fa[b][i];

        }

    if (a==b) return a;

    else return fa[a][0];

}

void modify(int rt,int l,int r,int col)//修改区间色彩 

{

    push_down(rt);

    int L=tree[rt].l,R=tree[rt].r;

    if (L==l&&R==r)

    {

        tree[rt].data=1;

        tree[rt].lc=tree[rt].rc=col;

        tree[rt].mark=col;

        return;

    }

    int mid=(L+R)>>1;

    if (r<=mid) modify(ln,l,r,col);

    else

    if (l>mid) modify(rn,l,r,col);

    else

    {

        modify(ln,l,mid,col);

        modify(rn,mid+1,r,col);

    }

    push_up(rt);

}

void Modify(int a,int b,int col)//修改两点间路径色彩 

{

    while(chain[a]!=chain[b])

    {

        modify(1,num[chain[a]],num[a],col);

        a=fa[chain[a]][0];

    }

    modify(1,num[b],num[a],col);//在把链上提以后a在b的左边

    //(差不多就是这个意思自己懂就行...) 

}

int query(int rt,int l,int r)//查询区间色彩段数目 

{

    push_down(rt);

    int L=tree[rt].l,R=tree[rt].r;

    if (L==l&&R==r) return tree[rt].data;

    int mid=(L+R)>>1;

    if (r<=mid) return query(ln,l,r);

    else

    if (mid<l) return query(rn,l,r);

    else

    {

        /*if (tree[ln].rc==tree[rn].lc)

            return query(ln,l,mid)+query(rn,mid+1,r)⑴;

        else

            return query(ln,l,mid)+query(rn,mid+1,r);*/

    }

}

int pointcolor(int rt,int x)//查询某个点的色彩 （可以看作是查询权值）

{

    push_down(rt);

    int L=tree[rt].l,R=tree[rt].r;

    if (L==R) return tree[rt].lc;

    int mid=(L+R)>>1;

    if (x<=mid) return pointcolor(ln,x);

    else return pointcolor(rn,x);

}

int Query(int a,int b)//查询两点间路径色彩段数目 

{

    int ret=0;

    while (chain[a]!=chain[b])

    {

        ret+=query(1,num[chain[a]],num[a]);

/*      if (pointcolor(1,num[chain[a]])==pointcolor(1,num[fa[chain[a]][0]]))

            ret--;*/

        a=fa[chain[a]][0];

    }

    ret+=query(1,num[b],num[a]);

    return ret;

}

int main()

{

    scanf("%d%d",&n,&m);

    for (int i=1;i<=n;i++)

        scanf("%d",&co[i]);

    for (int i=1;i<n;i++)

    {

        scanf("%d%d",&a,&b);

        insert(a,b);insert(b,a);

    }

    dfs1(1);

    dfs2(1,1);

    build();

    for (int i=1;i<=n;i++)

        modify(1,num[i],num[i],co[i]);

    for (int i=1;i<=m;i++)

    {

        scanf("%s",ch);

        if (ch[0]=='Q')

        {

            scanf("%d%d",&a,&b);

            int t=lca(a,b);

            printf("%d

",Query(a,t)+Query(b,t)-1);

        }

        else

        {

            scanf("%d%d%d",&a,&b,&color);

            int t=lca(a,b);

            Modify(a,t,color);

            Modify(b,t,color);

        }

    }

}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！

波比源码 » [置顶] 【整合】树链剖分模板（线段树维护）

分享到：

41 评论

波员 Organik Hit

2023年3月1日 at 上午9:15

Hi, just required you to know I he added your site to my Google bookmarks due to your layout. But seriously, I believe your internet site has 1 in the freshest theme I??ve came across. Web Site Hit Arttırma | Organik Hit Programı | Organik Hit – Yüksek Hit Aktif Hit Kullanıcı Yola Organik Hit
波员 Cami Halısı Adana

2023年3月2日 at 上午9:45

Everything is very open and very clear explanation of issues. was truly information. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 cami halısı balikesir

2023年3月2日 at 上午10:01

Thank you for content. Area rugs and online home decor store. Hello Administ . Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Afyon

2023年3月2日 at 上午10:23

Hi, just required you to know I he added your site to my Google bookmarks due to your layout. But seriously, I believe your internet site has 1 in the freshest theme I??ve came across.Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Kocaeli

2023年3月3日 at 下午3:22

Great post thank you. Hello Administ . Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Mersin

2023年3月3日 at 下午4:11

Thank you great posting about essential oil. Hello Administ . Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı izmir

2023年3月3日 at 下午4:13

Hi, just required you to know I he added your site to my Google bookmarks due to your layout. But seriously, I believe your internet site has 1 in the freshest theme I??ve came across. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Rize

2023年3月3日 at 下午4:21

Hi, just required you to know I he added your site to my Google bookmarks due to your layout. But seriously, I believe your internet site has 1 in the freshest theme I??ve came across. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Kahramanmaraş

2023年3月3日 at 下午4:26

Thank you for great content. Hello Administ. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Malatya

2023年3月3日 at 下午4:31

Thank you for content. Area rugs and online home decor store. Hello Administ . Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Mardin

2023年3月3日 at 下午4:34

Everything is very open and very clear explanation of issues. was truly information. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Isparta

2023年3月3日 at 下午4:39

Everything is very open and very clear explanation of issues. was truly information. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Sinop

2023年3月3日 at 下午4:41

After all, what a great site and informative posts, I will upload inbound link – bookmark this web site? Regards, Reader. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Nevşehir

2023年3月3日 at 下午4:46

Great post thank you. Hello Administ . Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Kars

2023年3月3日 at 下午4:49

Thank you for great information. Hello Administ . Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Ordu

2023年3月3日 at 下午4:59

Hello! I could have sworn I’ve been to this blog before but after browsing through some of the post I realized it’s new to me. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı istanbul

2023年3月3日 at 下午5:04

Great post thank you. Hello Administ . Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Kayseri

2023年3月3日 at 下午5:06

Hi, just required you to know I he added your site to my Google bookmarks due to your layout. But seriously, I believe your internet site has 1 in the freshest theme I??ve came across. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Samsun

2023年3月3日 at 下午5:08

Great post thank you. Hello Administ . Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Göbekli cami halısı

2023年3月3日 at 下午5:48

Thank you for great content. Hello Administ. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Çanakkale

2023年3月3日 at 下午6:36

Great post thank you. Hello Administ . Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Bursa

2023年3月3日 at 下午6:55

After all, what a great site and informative posts, I will upload inbound link – bookmark this web site? Regards, Reader. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Eskişehir

2023年3月3日 at 下午6:58

Everything is very open and very clear explanation of issues. was truly information. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Giresun

2023年3月3日 at 下午7:19

Everything is very open and very clear explanation of issues. was truly information. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Gaziantep

2023年3月3日 at 下午7:57

Everything is very open and very clear explanation of issues. was truly information. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Hakkari

2023年3月3日 at 下午8:32

After all, what a great site and informative posts, I will upload inbound link – bookmark this web site? Regards, Reader. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Çorum

2023年3月3日 at 下午8:42

Thank you great post. Hello Administ . Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Edirne

2023年3月3日 at 下午8:43

Thank you for great article. Hello Administ . Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Denizli

2023年3月3日 at 下午8:57

Hi, just required you to know I he added your site to my Google bookmarks due to your layout. But seriously, I believe your internet site has 1 in the freshest theme I??ve came across. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Cami Halısı Elazığ

2023年3月3日 at 下午9:47

Great post thank you. Hello Administ . Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Onwin Güncel Giriş

2023年3月7日 at 上午7:25

Thank you great posting about essential oil. Hello Administ . Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Onwin

2023年3月7日 at 上午7:27

Hello! I could have sworn I’ve been to this blog before but after browsing through some of the post I realized it’s new to me. Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…
波员 Onwin Güncel Giriş

2023年3月7日 at 上午7:30

Nice article inspiring thanks. Hello Administ . Hacklink , Hacklink panel , Hacklink al Onwin , Onwin Giriş , Onwin Güncel Giriş , Onwin Resmi Sitesi. <a href="https://sites.google.com/view/onwinnguncel/" title="onw
波员 onwin giriş

2023年3月7日 at 上午9:11

Great post thank you. Hello Administ . Hacklink , Hacklink panel , Hacklink al Hacklink panel
波员 Onwin Güncel Giriş

2023年3月9日 at 下午1:20

Thank you great posting about essential oil. Hello Administ . Onwin , Onwin Giriş , Onwin Güncel Giriş , Onwin Yeni Adres , onwin
波员 Onwin Güncel Giriş

2023年3月9日 at 下午1:26

Thank you great post. Hello Administ . Onwin , Onwin Giriş , Onwin Güncel Giriş , Onwin Yeni Adres , onwin
波员 Onwin Giriş

2023年3月9日 at 下午1:30

Great post thank you. Hello Administ . Onwin , Onwin Giriş , Onwin Güncel Giriş , Onwin Yeni Adres , onwin
波员 Casibom

2023年3月11日 at 下午6:05

I really love to read such an excellent article. Helpful article. Hello Administ . Casibom , Casibom Giriş , Casibom Güncel Giriş , Casibom yeni adres . <a href="https://seowebtasarim.net/casibom/" title="Casibin
波员 Karaca Cami Halıları

2023年3月18日 at 上午4:46

I really love to read such an excellent article. Helpful article. Hello Administ .
波员 Cami Halıları

2023年3月18日 at 上午6:25

Thank you great posting about essential oil. Hello Administ .
波员 onwin güncel giriş

2023年3月18日 at 上午10:41

Thank you for great article. Hello Administ . Hacklink , Hacklink panel , Hacklink al Hacklink panel