BZOJ-2243[SDOI2011]染色

[文章目录]

Description

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

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

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

请你写一个程序依次完成这m个操作。n<=100000,m<=100000

 树链剖分+线段树染色问题。第二次写树链剖分。
树链剖分,感觉还是dfs的时候少传参比较好吧。于是吧pre改成了fa[]。
线段树还是写结构体里比较清真吧。维护四个参数。
left[]-左端点颜色,right[]-右端点颜色,num[]区间颜色段数量,lazy[]染色延迟标记。建树的时候直接就将点的颜色赋给lazy就好了吧。
然后就是码力和思想缜密的问题了。感觉还行吧。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 101000
int n,m,val[N];
char st[10];
int head[N],to[N<<1],nxt[N<<1],cnt;
void add(int x,int y)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; 
}
int fa[N],deep[N],siz[N],son[N];
void dfs1(int x)
{
    int k=-1<<30;siz[x]++;
    for(int y,i=head[x];i;i=nxt[i])
    {
        y=to[i];
        if(y!=fa[x])
        {
            fa[y]=x;deep[y]=deep[x]+1;
            dfs1(y);
            siz[x]+=siz[y];
            if(siz[y]>k) k=siz[y],son[x]=y;
        }
    }
}
int tre[N],tid[N],top[N],tot;
void dfs2(int x,int anc)
{
    tre[++tot]=val[x];tid[x]=tot;top[x]=anc;
    if(son[x]) dfs2(son[x],anc);
    for(int i=head[x];i;i=nxt[i])
        if(to[i]!=fa[x]&&to[i]!=son[x])
            dfs2(to[i],to[i]);
}
struct seg
{
    int num[N<<2],lazy[N<<2],left[N<<2],right[N<<2];
    seg(){memset(lazy,-1,sizeof(lazy));}
    void pushup(int pos)
    {
        left[pos]=left[pos<<1];right[pos]=right[pos<<1|1];
        num[pos]=num[pos<<1]+num[pos<<1|1];
        if(right[pos<<1]==left[pos<<1|1]) num[pos]--;
    }
    void pushdown(int pos)
    {
        if(lazy[pos]!=-1)
        {
            if(num[pos<<1]) {left[pos<<1]=right[pos<<1]=lazy[pos<<1]=lazy[pos];num[pos<<1]=1;}
            if(num[pos<<1|1]) {left[pos<<1|1]=right[pos<<1|1]=lazy[pos<<1|1]=lazy[pos];num[pos<<1|1]=1;}
            lazy[pos]=-1;
        }
    }
    void build(int pos,int l,int r)
    {
        if(l==r){left[pos]=right[pos]=lazy[pos]=tre[r];num[pos]=1;return ;}
        int mid=l+r>>1;
        build(pos<<1,l,mid);build(pos<<1|1,mid+1,r);
        pushup(pos);
    }
    int query_pos(int pos,int l,int r,int x)
    {
        if(lazy[pos]!=-1) return lazy[pos];
        int mid=l+r>>1;
        if(x<=mid) return query_pos(pos<<1,l,mid,x);
        else return query_pos(pos<<1|1,mid+1,r,x);
    }
    int query(int pos,int l,int r,int x,int y)
    {
        if(x<=l&&y>=r) return num[pos];
        int mid=l+r>>1;pushdown(pos);
        if(y<=mid) return query(pos<<1,l,mid,x,y);
        if(x>mid) return query(pos<<1|1,mid+1,r,x,y);
        if(right[pos<<1]==left[pos<<1|1])
            return query(pos<<1,l,mid,x,y)+query(pos<<1|1,mid+1,r,x,y)-1;
        else return query(pos<<1,l,mid,x,y)+query(pos<<1|1,mid+1,r,x,y);
    }
    void fix(int pos,int l,int r,int x,int y,int col)
    {
        if(x<=l&&y>=r) {left[pos]=right[pos]=lazy[pos]=col;num[pos]=1; return ; }
        int mid=l+r>>1; pushdown(pos);
        if(y<=mid) fix(pos<<1,l,mid,x,y,col);
        else if(x>mid) fix(pos<<1|1,mid+1,r,x,y,col);
        else fix(pos<<1,l,mid,x,y,col),fix(pos<<1|1,mid+1,r,x,y,col);
        pushup(pos);
    }
}T1;
void Fix()
{
    int x,y,c; scanf("%d%d%d",&x,&y,&c);
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        T1.fix(1,1,n,tid[top[x]],tid[x],c);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]) swap(x,y);
    T1.fix(1,1,n,tid[x],tid[y],c);
}
void Query()
{
    int c[2],flag,col[2],re=0;
    col[0]=col[1]=-1;
    scanf("%d%d",&c[0],&c[1]);
    while(top[c[0]]!=top[c[1]])
    {
        if(deep[top[c[0]]]<deep[top[c[1]]]) flag=1;
        else flag=0;
        re+=T1.query(1,1,n,tid[top[c[flag]]],tid[c[flag]]);
        if(T1.query_pos(1,1,n,tid[c[flag]])==col[flag]) re--;
        col[flag]=T1.query_pos(1,1,n,tid[top[c[flag]]]);
        c[flag]=fa[top[c[flag]]];//第一次写成c[flag]=fa[c[flag]],WA-1
    }
    if(deep[c[0]]>deep[c[1]]) swap(c[0],c[1]),swap(col[0],col[1]);//第二次没交换col[],WA-2
    re+=T1.query(1,1,n,tid[c[0]],tid[c[1]]);
    re-=(T1.query_pos(1,1,n,tid[c[0]])==col[0])+(T1.query_pos(1,1,n,tid[c[1]])==col[1]);
    printf("%d\n",re);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&val[i]);
    for(int x,y,i=1;i<n;i++) {scanf("%d%d",&x,&y); add(x,y); add(y,x); }
    deep[1]=1;dfs1(1);dfs2(1,1); T1.build(1,1,n);
    while(m--)
    {
        scanf("%s",st);
        switch(st[0])
        {
            case 'C':Fix();break;
            case 'Q':Query();break;
        }
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注