欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【bzoj2243】[SDOI2011]染色树链剖分(区间合并处理)

程序员文章站 2022-03-10 14:33:07
2243: [sdoi2011]染色 time limit: 20 sec memory limit: 512 mb submit: 5143 solved: 1919 [submit][statu...

2243: [sdoi2011]染色
time limit: 20 sec memory limit: 512 mb
submit: 5143 solved: 1919
[submit][status][discuss]
description

给定一棵有n个节点的无根树和m个操作,操作有2类:

1、将节点a到节点b路径上所有点都染成颜色c;

2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”、“222”和“1”。

请你写一个程序依次完成这m个操作。

input

第一行包含2个整数n和m,分别表示节点数和操作数;

第二行包含n个正整数表示n个节点的初始颜色

下面 行每行包含两个整数x和y,表示x和y之间有一条无向边。

下面 行每行描述一个操作:

“c a b c”表示这是一个染色操作,把节点a到节点b路径上所有点(包括a和b)都染成颜色c;

“q a b”表示这是一个询问操作,询问节点a到节点b(包括a和b)路径上的颜色段数量。

output

对于每个询问操作,输出一行答案。

数n<=10^5,操作数m<=10^5,所有的颜色c为整数且在[0, 10^9]之间。

题意
一颗树,节点各有颜色,1.修改区间颜色;2.询问区间的颜色段数;

思路
1.区间操作--》线段树;
2.给棵树--》树剖(dfs*2 找重链,赋树剖的序);
3.询问连续区间段数:
用线段树节点维护的信息:
1.num本段区间个数;
2.l本段左端颜色;
3.r本段右端颜色;
(用于判定区间合并的处理)

if(t[lson].r==t[rson].l) t[id].num--;

*注意颜色可为0,故*lazy初始-1,或col++;

代码

#include
#include
#include
#include
#define lson (id*2)
#define rson (id*2+1)
using namespace std;
int n,m;
struct node{
    int l,r,num;
    int lazy;
}t[800005];
vector lin[100005];
int xx,yy;
int a[100005],b[100005];
int in[100005],out[100005];
int size[100005];
int dep[100005];
int ans;
int top[100005];
int son[100005];
int fa[100005];
int tot;
void dfs1(int id,int pre)//找重链
{
    fa[id]=pre;
    size[id]=1;
    son[id]=-1;
    dep[id]=dep[pre]+1;
    int len=lin[id].size();
    for(int i=0;ir||r=l&&r<=r)
    {


        t[id].l=t[id].r=v;
        t[id].num=1;
        t[id].lazy=v;
        return ;
    }

    int mid=(l+r)>>1;
    push_down(id);
    add(lson,l,mid,l,r,v);
    add(rson,mid+1,r,l,r,v);
    push_up(id);
}
void query(int id,int l,int r,int l,int r,int ttt)
{

    if(l>r||r=l&&r<=r)
    {

        if(ttt!=2)
        ans+=t[id].num;

        if(l==r) 
        xx=t[id].l;
        return ;
    }
    int mid=(l+r)>>1;
    push_down(id);
    if(r<=mid) query(lson,l,mid,l,r,ttt);
    else if(l>mid)
    query(rson,mid+1,r,l,r,ttt);
    else
    {
        if(t[lson].r==t[rson].l) ans--;//区间连接处!
        query(lson,l,mid,l,r,ttt);
        query(rson,mid+1,r,l,r,ttt);
    }
}
void build(int id,int l,int r)
{
    if(l==r)
    {
        t[id].num=1;

        t[id].l=t[id].r=b[l];

        return ;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    push_up(id);

}
int main()
{
    int aa,bb,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i]++;
    }
    for(int i=1;idep[bb]) swap(aa,bb);        
            add(1,1,tot,in[aa],in[bb],v);


        }
        if(s[0]=='q')
        {
            ans=0;
            scanf("%d%d",&aa,&bb);

            while(top[aa]!=top[bb])
            {               

                if(dep[top[aa]]dep[bb]) swap(aa,bb);
            query(1,1,tot,in[aa],in[bb],1);
            printf("%d\n",ans);
        }
    }
}

 

 

[top[bb]])>
;i++)>
)>
)>
;i++)>