【BZOJ 2243】【SDOI 2011】染色 / 题解

【BZOJ 2243】【SDOI 2011】染色 / 题解

BZOJ原题地址

洛谷原题地址

思路

树上路径修改,当然是选择树链剖分这种没有思维含量的暴力了啊。。。
颜色段的问题,考虑用线段树来维护。每个节点储存区间的颜色段数以及左右端点的颜色种类。当我们要把两个区间的信息合并的时候,只需要判断一下端点处颜色来决定要不要将颜色段数减一就行了。。。
我的写法的一个问题是,在路径查询的时候,因为我们得到的是一个“人”字形的路径,需要分别储存左边和右边的信息,加上最后在同一条重链上得到的区间信息,一共有三个区间需要合并。

如图,询问$X$到$Y$的路径上的颜色段时,我们先分别将$X$和$Y$移动到了$A$和$B$,同时记录了$X$经过的路径上的信息$lres$,和$Y$经过的路径上的信息$rres$。最后,我们获得了位于同一条重链上的$A$,$B$之间的信息$res$。
由于树链剖分的性质,我们知道区间的左端点深度更小,所以$lres$,$rres$,$res$在上图状态下的左端点分别为$A$,$B$和$B$,所以在合并的时候,需要交换一下$rres$的左右端点信息。

代码实现

// Paint.cpp: 定义控制台应用程序的入口点。
//XG_Zepto, 5/15/2018. All rights reserved.

//#include "stdafx.h"
#include 
#include 
#include 
#include 
#include 
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((r+l)>>1)
#define NewN(k) Node(1,k,k) 
#define maxn 100100
using namespace std;
struct Edge{
    int to,next;
    Edge(int a=0,int b=0){
        to=a,next=b;
    }
}l[maxn*2];
struct Node{
    int num,lco,rco;
    Node(int a=0,int b=0,int c=0){
        num=a,lco=b,rco=c;
    }
}tree[maxn*4];
int head[maxn],cnt,n,m,top[maxn],fa[maxn],id[maxn],col[maxn];
int son[maxn],siz[maxn],dep[maxn],nco[maxn],nid,lazy[maxn*4];
inline void Add(int x,int y){
    l[++cnt]=Edge(y,head[x]);
    head[x]=cnt;
}
inline void Pre_Work(int u,int f){
    dep[u]=dep[f]+1;fa[u]=f;siz[u]=1;
    int maxsiz=-1;
    for (int i=head[u];i;i=l[i].next){
        int v=l[i].to;if (v==f) continue;
        Pre_Work(v,u);siz[u]+=siz[v];
        if (siz[v]>maxsiz) maxsiz=siz[v],son[u]=v;
    }
}
inline void Re_Build(int u,int topf){
    id[u]=++nid,nco[nid]=col[u],top[u]=topf;
    if (son[u]) Re_Build(son[u],topf);
    for (int i=head[u];i;i=l[i].next){
        int v=l[i].to;if (v==fa[u]||v==son[u]) continue;
        Re_Build(v,v);
    }
}
inline void Swap(Node &x){
    swap(x.lco,x.rco);
}
inline void Pushup(int p){
    if (tree[ls].lco==0){
        tree[p]=tree[rs];
        return;
    }
    if (tree[rs].lco==0){
        tree[p]=tree[ls];
        return;
    }
    int sum=tree[ls].num+tree[rs].num;
    if (tree[ls].rco==tree[rs].lco) sum--;
    tree[p]=Node(sum,tree[ls].lco,tree[rs].rco);
}
inline Node Merge(Node x,Node y){
    if (x.lco==0) return y;
    if (y.lco==0) return x;
    int cut=(x.rco==y.lco);
    return Node(x.num+y.num-cut,x.lco,y.rco);
}
inline void Set_Up(int l,int r,int p){
    if (l==r){tree[p]=Node(1,nco[l],nco[r]);return;}
    Set_Up(l,mid,ls);Set_Up(mid+1,r,rs);Pushup(p);
}
inline void Pushdown(int p){
    int te=lazy[p];lazy[p]=0;
    Node tem=NewN(te);
    tree[ls]=tree[rs]=tem;
    lazy[ls]=lazy[rs]=te;
}
inline Node Query(int l,int r,int L,int R,int p){
    if (l>R||r=L&&r<=R) return tree[p];
    if (lazy[p]) Pushdown(p);
    return Merge(Query(l,mid,L,R,ls),Query(mid+1,r,L,R,rs));
}
inline void Change(int l,int r,int L,int R,int k,int p){
    if (l>R||r=L&&r<=R){
        tree[p]=NewN(k);
        lazy[p]=k;
        return;
    }
    if (lazy[p]) Pushdown(p);
    Change(l,mid,L,R,k,ls);
    Change(mid+1,r,L,R,k,rs);
    Pushup(p);
}
inline void Path_Query(int x,int y){
    Node lres=rres=res=Node(0,0,0);
    while(top[x]!=top[y]){
        if (dep[top[x]]>dep[top[y]]){
            lres=Merge(Query(1,n,id[top[x]],id[x],1),lres);
            x=fa[top[x]];
        }
       else{
            rres=Merge(Query(1,n,id[top[y]],id[y],1),rres);
            y=fa[top[y]];
        }
    }
    if (dep[x]dep[y]) swap(x,y);
    Change(1,n,id[x],id[y],k,1);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>col[i];
    for (int i=1,t1,t2;i<=n-1;i++)
        cin>>t1>>t2,Add(t1,t2),Add(t2,t1);
    Pre_Work(1,0);Re_Build(1,1);Set_Up(1,n,1);char op;
    for (int i=1;i<=m;i++){
        cin>>op;
        if (op=='Q'){
            int t1,t2;cin>>t1>>t2;
            Path_Query(t1,t2);
        }
        else{
            int t1,t2,t3;cin>>t1>>t2>>t3;
            Path_Change(t1,t2,t3);
        }
    }
    return 0;
}
Show Comments