[BZOJ2243/Luogu2486][SDOI2011]染色(树链剖分,线段树)

发布于 2018-04-17  66 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2243/Luogu2486][SDOI2011]染色(树链剖分,线段树)

Description

给定一棵有n个节点的无根树和m个操作,操作有2类:
1、将节点a到节点b路径上所有点都染成颜色c;
2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。

Tag

树链剖分,线段树

解决思路

将树树链剖分后,考虑用线段树维护连续区间上的颜色段数量,那么合并两个区间时,对结果有影响的即为端点颜色,记录下来合并。在树链剖分跳链的时候,也记录下颜色 。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define lson (now<<1)
#define rson (lson|1)

const int maxN=100101;
const int maxM=maxN*2;
const int inf=2147483647;

class Data
{
public:
    int cnt;
    int left,right;
    int cover;
    Data(){
        cover=-1;
    }
};

int n,m;
int Col[maxN];
Data S[maxN<<2];
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
int Size[maxN],Hson[maxN],Fa[maxN],Top[maxN],Depth[maxN];
int idcnt,Id[maxN],Di[maxN];

Data operator + (Data A,Data B);
void Add_Edge(int u,int v);
void dfs1(int u,int fa);
void dfs2(int u,int top);
void Build(int now,int l,int r);
void Modify_TC(int u,int v,int key);
int Query_TC(int u,int v);
void PushDown(int now);
void Modify_Seg(int now,int l,int r,int ql,int qr,int key);
Data Query_Seg(int now,int l,int r,int ql,int qr);

int main()
{
    ios::sync_with_stdio(false);
    mem(Head,-1);

    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>Col[i];
    for (int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        Add_Edge(u,v);Add_Edge(v,u);
    }
    Depth[1]=1;
    dfs1(1,1);dfs2(1,1);//树链剖分
    Build(1,1,n);

    while (m--)
    {
        char opt;cin>>opt;
        if (opt=='C')
        {
            int u,v,col;cin>>u>>v>>col;
            Modify_TC(u,v,col);
        }
        if (opt=='Q')
        {
            int u,v;cin>>u>>v;
            cout<<Query_TC(u,v)<<endl;
        }
    }
    return 0;
}

Data operator + (Data A,Data B)
{
    Data Ret;
    Ret.left=A.left;Ret.right=B.right;
    Ret.cnt=A.cnt+B.cnt-(A.right==B.left);//当端点有色相同时,颜色段个数-1
    return Ret;
}

void Add_Edge(int u,int v)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
    return;
}

void dfs1(int u,int fa)
{
    Size[u]=1;Hson[u]=0;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (V[i]!=fa)
        {
            Fa[V[i]]=u;Depth[V[i]]=Depth[u]+1;
            dfs1(V[i],u);
            Size[u]+=Size[V[i]];
            if (Size[Hson[u]]<Size[V[i]]) Hson[u]=V[i];
        }
    return;
}

void dfs2(int u,int top)
{
    Top[u]=top;Id[u]=++idcnt;Di[idcnt]=u;
    if (Hson[u]==0) return;
    dfs2(Hson[u],top);
    for (int i=Head[u];i!=-1;i=Next[i])
        if ((V[i]!=Fa[u])&&(V[i]!=Hson[u]))
            dfs2(V[i],V[i]);
    return;
}

void Build(int now,int l,int r)//建树
{
    if (l==r)
    {
        S[now].cnt=1;S[now].left=S[now].right=Col[Di[l]];
        return;
    }
    int mid=(l+r)>>1;
    Build(lson,l,mid);Build(rson,mid+1,r);
    S[now]=S[lson]+S[rson];
    return;
}

void Modify_TC(int u,int v,int key)//修改
{
    while (Top[u]!=Top[v])
    {
        if (Depth[Top[u]]<Depth[Top[v]]) swap(u,v);
        Modify_Seg(1,1,n,Id[Top[u]],Id[u],key);
        u=Fa[Top[u]];
    }
    if (Depth[u]>Depth[v]) swap(u,v);
    Modify_Seg(1,1,n,Id[u],Id[v],key);
    return;
}

int Query_TC(int u,int v)//查询
{
    int Ret=0,lastcolu=-1,lastcolv=-1;//注意这里要记录上一次的颜色段数量
    while (Top[u]!=Top[v])
    {
        if (Depth[Top[u]]<Depth[Top[v]]) swap(u,v),swap(lastcolu,lastcolv);//两个要同时交换
        Data G=Query_Seg(1,1,n,Id[Top[u]],Id[u]);
        Ret+=G.cnt-(G.right==lastcolu);
        lastcolu=G.left;
        u=Fa[Top[u]];
    }
    if (Depth[u]>Depth[v]) swap(u,v),swap(lastcolu,lastcolv);
    Data G=Query_Seg(1,1,n,Id[u],Id[v]);
    Ret+=G.cnt-(G.left==lastcolu)-(G.right==lastcolv);
    return Ret;
}

void PushDown(int now)
{
    if (S[now].cover!=-1)
    {
        int col=S[now].cover;
        S[lson].cnt=1;S[lson].left=S[lson].right=col;S[lson].cover=col;
        S[rson].cnt=1;S[rson].left=S[rson].right=col;S[rson].cover=col;
        S[now].cover=-1;
    }
    return;
}

void Modify_Seg(int now,int l,int r,int ql,int qr,int key)
{
    if ((l==ql)&&(r==qr))
    {
        S[now].cover=S[now].left=S[now].right=key;
        S[now].cnt=1;S[now].cover=key;
        return;
    }
    PushDown(now);
    int mid=(l+r)>>1;
    if (qr<=mid) Modify_Seg(lson,l,mid,ql,qr,key);
    else if (ql>=mid+1) Modify_Seg(rson,mid+1,r,ql,qr,key);
    else
    {
        Modify_Seg(lson,l,mid,ql,mid,key);
        Modify_Seg(rson,mid+1,r,mid+1,qr,key);
    }
    S[now]=S[lson]+S[rson];
    return;
}

Data Query_Seg(int now,int l,int r,int ql,int qr)
{
    if ((l==ql)&&(r==qr)) return S[now];
    PushDown(now);
    int mid=(l+r)>>1;
    if (qr<=mid) return Query_Seg(lson,l,mid,ql,qr);
    else if (ql>=mid+1) return Query_Seg(rson,mid+1,r,ql,qr);
    else return Query_Seg(lson,l,mid,ql,mid)+Query_Seg(rson,mid+1,r,mid+1,qr);
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2243/Luogu2486][SDOI2011]染色(树链剖分,线段树)


HNCJ OIer