染色[SDOI2011]

题目描述

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

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

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

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

输入

第一行包含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）路径上的颜色段数量。

输出

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

样例输入

6 5

2 2 1 2 1 1

1 2

1 3

2 4

2 5

2 6

Q 3 5

C 2 1 1

Q 3 5

C 5 1 2

Q 3 5

样例输出

提示

N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。

题解

从开始打就感觉这题绝对会白打，果然如此。刚开始学树剖，对题型的了解还很不全面。

    1.刚开始接触的 A难存的情缘 和 C货车运输 是边权下放、边权修改、路径查询

         if(id[x]<id[y])

              res=qd(res,query(id[x]+1,id[y],1,1,n))；

         void change(int p,int t,int r,int z,int y)

         {

                if(z==y)

                {

                  mx[r]=t;

                  return;

                }

                int mid=(z+y)/2;

                if(p<=mid)  change(p,t,r*2,z,mid);

                else change(p,t,r*2+1,mid+1,y);

                mx[r]=qd(mx[r*2],mx[r*2+1]);

          }

    2.后来做的 B树上操作 和 E 树的统计 是点权修改、子树修改、路径查询，用到延迟标记和dfs序

         if(id[x]<=id[y])  res+=query(id[x],id[y],1,1,n);

         void change(int fr,int to,ll a,int r,int z,int y)

         {

            if(fr<=z&&to>=y)

            {

                lazy[r]+=a;

                t[r].sm+=(long long)(y-z+1)*a;

                return;

            }

            pushdown(r);

            int mi=(t[r].le+t[r].ri)>>1;

            if(fr<=mi)  change(fr,to,a,r<<1,z,mi);

            if(to>mi)  change(fr,to,a,(r<<1)|1,mi+1,y);

            pushup(r);

         }

    3.一直到今天的考试，我才明白change函数也可以像query一样分层操作。路径修改，路径查询，并且加了方向与合并。特别的是，把链上翻时比较链端和链端的父亲，来确认是否能合并一个色段。

       query(id[fa[fx]],id[fa[fx]],1,1,n);

       zd2=zd1;

       query(id[fx],id[fx],1,1,n);

       if(zd1==zd2)  res--;

    因为有hotel的经验，在线段树里记录左右端颜色并不难想到，延迟标记也是理所当然。其他步骤都比较容易，只有没打过的路径修改和查询合并是问题所在。只要fx和fa[fx]颜色相同，就可以合并一个色块。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

using namespace std;

const int sj=;

int n,m,ys[sj],h[sj],e,a1,a2,a3,zd1,zd2;

char ss;

struct B

{

     int u,v,ne;

}b[sj*];

void add(int x,int y)

{

     e++;

     b[e].ne=h[x];

     b[e].u=x;

     b[e].v=y;

     h[x]=e;

}

void init()

{

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

     memset(h,-,sizeof(h));

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

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

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

     {

        scanf("%d%d",&a1,&a2);

        add(a1,a2);

        add(a2,a1);

     }

}

int fa[sj]={},son[sj]={},size[sj],dep[sj]={};

void dfs1(int x)

{

     size[x]=;

     for(int i=h[x];i!=-;i=b[i].ne)

     {

        int to=b[i].v;

        if(to!=fa[x])

        {

           fa[to]=x;

           dep[to]=dep[x]+;

           dfs1(to);

           size[x]+=size[to];

           if(size[to]>size[son[x]])  son[x]=to;

        }

     }

}

int top[sj],pos[sj],id[sj],cnt,sd[sj];

void dfs2(int x,int y)

{

     top[x]=y;

     id[x]=++cnt;

     sd[id[x]]=x;

     pos[cnt]=x;

     if(son[x])  dfs2(son[x],y);

     for(int i=h[x];i!=-;i=b[i].ne)

     {

        int to=b[i].v;

        if(to!=fa[x]&&to!=son[x])

          dfs2(to,to);

     }

}

struct Tree

{

    int ds,zj,yj,zs,ys;

}t[sj*];

int lazy[sj*];

void build(int x,int z,int y)

{

     t[x].zj=z;

     t[x].yj=y;

     if(z==y)

     {

        t[x].ds=;

        t[x].zs=t[x].ys=ys[pos[z]];

        return;

     }

     int mid=(z+y)>>,ze=x<<,ye=(x<<)|;

     build(ze,z,mid);

     build(ye,mid+,y);

     t[x].ds=t[ze].ds+t[ye].ds;

     if(t[ze].ys==t[ye].zs)

        t[x].ds--;

     t[x].ys=t[ye].ys;

     t[x].zs=t[ze].zs;

}

void jh(int &x,int &y)

{

     int jy=y;

     y=x;

     x=jy;

}

void pushdown(int x)

{

     if(lazy[x]!=-)

     {

         int ze=x<<,ye=(x<<)|;

         lazy[ze]=lazy[ye]=lazy[x];

         t[ze].ds=t[ye].ds=;

         t[ze].zs=t[ze].ys=lazy[x];

         t[ye].zs=t[ye].ys=lazy[x];

         lazy[x]=-;

     }

}

void pushup(int x)

{

     int ze=x<<,ye=(x<<)|;

     t[x].ds=t[ze].ds+t[ye].ds;

     if(t[ze].ys==t[ye].zs)

        t[x].ds--;

     t[x].ys=t[ye].ys;

     t[x].zs=t[ze].zs;

}

int query(int s,int to,int r,int z,int y)

{

    if(s==z&&to==y)

    {

       zd1=t[r].zs;

       return t[r].ds;

    }

    pushdown(r);

    int mid=(z+y)>>;

    int ze=r<<,ye=(r<<)|;

    if(to<=mid) return query(s,to,ze,z,mid);

    if(s>mid)   return query(s,to,ye,mid+,y);

    int res=query(s,mid,ze,z,mid)+query(mid+,to,ye,mid+,y);

    if(t[ze].ys==t[ye].zs) res--;

    return res;

}

int Q(int x,int y)

{

    int res=,fx=top[x],fy=top[y];

    while(fx^fy)

    {

       if(dep[fx]<dep[fy])

       {

          jh(x,y);

          jh(fx,fy);

       }

       res+=query(id[fx],id[x],,,n);

       query(id[fa[fx]],id[fa[fx]],,,n);

       zd2=zd1;

       query(id[fx],id[fx],,,n);

       if(zd1==zd2)  res--;

       x=fa[fx];

       fx=top[x];

    }

    if(dep[x]>dep[y])  jh(x,y);

    if(id[x]<=id[y])  res+=query(id[x],id[y],,,n);

    return res;

}

void c(int s,int to,int a,int r,int z,int y)

{

    if(s==z&&to==y)

    {

        lazy[r]=a;

        t[r].ds=;

        t[r].ys=t[r].zs=a;

        return;

    }

    pushdown(r);

    int mid=(z+y)>>;

    int ze=r<<,ye=(r<<)|;

    if(to<=mid) c(s,to,a,ze,z,mid);

    if(s>mid)   c(s,to,a,ye,mid+,y);

    if(to>mid&&s<=mid)

    {

       c(s,mid,a,ze,z,mid);

       c(mid+,to,a,ye,mid+,y);

    }

    pushup(r);

}

void C(int x,int y,int a)

{

    int fx=top[x],fy=top[y];

    while(fx^fy)

    {

       if(dep[fx]<dep[fy])

       {

          jh(x,y);

          jh(fx,fy);

       }

       c(id[fx],id[x],a,,,n);

       x=fa[fx];

       fx=top[x];

    }

    if(dep[x]>dep[y])  jh(x,y);

    if(id[x]<=id[y])  c(id[x],id[y],a,,,n);

}

void cl()

{

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

     {

        scanf("%s",&ss);

        scanf("%d%d",&a1,&a2);

        if(ss=='Q')

           printf("%d\n",Q(a1,a2));

        if(ss=='C')

        {

           scanf("%d",&a3);

           C(a1,a2,a3);

        }

     }

}

int main()

{

    //freopen("t3.txt","r",stdin);

    init();

    dfs1();

    dfs2(,);

    memset(lazy,-,sizeof(lazy));

    build(,,n);

    cl();

    //while(1);

    return ;

}

巴特西

染色[SDOI2011]

题目描述

输入

输出

样例输入

样例输出

提示

最新文章

热门文章