染色[SDOI2011]

题目描述

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

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

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

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

输入

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

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

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

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

“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

样例输出

3

1

2

提示

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=100010;
int n,m,ys[sj],h[sj],e,a1,a2,a3,zd1,zd2;
char ss;
struct B
{
     int u,v,ne;
}b[sj*2];
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,-1,sizeof(h));
     for(int i=1;i<=n;i++)
        scanf("%d",&ys[i]);
     for(int i=1;i<n;i++)
     {
        scanf("%d%d",&a1,&a2);
        add(a1,a2);
        add(a2,a1);
     }
}
int fa[sj]={0},son[sj]={0},size[sj],dep[sj]={0};
void dfs1(int x)
{
     size[x]=1;
     for(int i=h[x];i!=-1;i=b[i].ne)
     {
        int to=b[i].v;
        if(to!=fa[x])
        {
           fa[to]=x;
           dep[to]=dep[x]+1;
           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!=-1;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*4];
int lazy[sj*4];
void build(int x,int z,int y)
{
     t[x].zj=z;
     t[x].yj=y;
     if(z==y)
     {
        t[x].ds=1;
        t[x].zs=t[x].ys=ys[pos[z]];
        return;
     }
     int mid=(z+y)>>1,ze=x<<1,ye=(x<<1)|1;
     build(ze,z,mid);
     build(ye,mid+1,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]!=-1)
     {
         int ze=x<<1,ye=(x<<1)|1;
         lazy[ze]=lazy[ye]=lazy[x];
         t[ze].ds=t[ye].ds=1;
         t[ze].zs=t[ze].ys=lazy[x];
         t[ye].zs=t[ye].ys=lazy[x];
         lazy[x]=-1;
     }
}
void pushup(int x)
{
     int ze=x<<1,ye=(x<<1)|1;
     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)>>1;
    int ze=r<<1,ye=(r<<1)|1;
    if(to<=mid) return query(s,to,ze,z,mid);
    if(s>mid)   return query(s,to,ye,mid+1,y);
    int res=query(s,mid,ze,z,mid)+query(mid+1,to,ye,mid+1,y);
    if(t[ze].ys==t[ye].zs) res--;
    return res;
}
int Q(int x,int y)
{
    int res=0,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],1,1,n);
       query(id[fa[fx]],id[fa[fx]],1,1,n);
       zd2=zd1;
       query(id[fx],id[fx],1,1,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],1,1,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=1;
        t[r].ys=t[r].zs=a;
        return;
    }
    pushdown(r);
    int mid=(z+y)>>1;
    int ze=r<<1,ye=(r<<1)|1;
    if(to<=mid) c(s,to,a,ze,z,mid);
    if(s>mid)   c(s,to,a,ye,mid+1,y);
    if(to>mid&&s<=mid)
    {
       c(s,mid,a,ze,z,mid);
       c(mid+1,to,a,ye,mid+1,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,1,1,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,1,1,n);
}
void cl()
{
     for(int i=1;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(1);
    dfs2(1,1);
    memset(lazy,-1,sizeof(lazy));
    build(1,1,n);
    cl();
    //while(1);
    return 0;
}
时间: 07-13

染色[SDOI2011]的相关文章

BZOJ 2243: [SDOI2011]染色 树链剖分

2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 1886  Solved: 752[Submit][Status] Description 给定一棵有n个节点的无根树和m个操作,操作有2类: 1.将节点a到节点b路径上所有点都染成颜色c: 2.询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”.“222”和“1”. 请你写一个程序依次完成这m个操作. In

bzoj 2243: [SDOI2011]染色 线段树区间合并+树链剖分

2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 7925  Solved: 2975[Submit][Status][Discuss] Description 给定一棵有n个节点的无根树和m个操作,操作有2类: 1.将节点a到节点b路径上所有点都染成颜色c: 2.询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”.“222”和“1”. 请你写一个程序依次完

bzoj-2243 2243: [SDOI2011]染色(树链剖分)

题目链接: 2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 6267  Solved: 2291 Description 给定一棵有n个节点的无根树和m个操作,操作有2类: 1.将节点a到节点b路径上所有点都染成颜色c: 2.询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”.“222”和“1”. 请你写一个程序依次完成这m个操作. Input 第一行包含

bzoj2243:[SDOI2011]染色

链剖就可以了.一开始的想法错了.但也非常接近了.妈呀调的要死...然后把字体再缩小一号查错起来比较容易QAQ. #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>

bzoj2243 [SDOI2011]染色 动态树

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 110000 int pre[N],ch[N][2]; int e[N],ne[N*2],v[N*2]; int nn,m; int col[N]; int lc[N],sm[N],rc[N],num[N]; int rt[N],n; int qu[N

2243: [SDOI2011]染色(树链剖分+线段树)

2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 8400  Solved: 3150[Submit][Status][Discuss] Description 给定一棵有n个节点的无根树和m个操作,操作有2类: 1.将节点a到节点b路径上所有点都染成颜色c: 2.询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”.“222”和“1”. 请你写一个程序依次完

BZOJ 2243: [SDOI2011]染色 树链剖分+线段树区间合并

2243: [SDOI2011]染色 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之间有一条无向边.

BZOJ 2243: [SDOI2011]染色 树链剖分 倍增lca 线段树

2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline/problem.php?id=2243 Description 给定一棵有n个节点的无根树和m个操作,操作有2类: 1.将节点a到节点b路径上所有点都染成颜色c: 2.询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”.“222”和“1”. 请你写

bzoj2243【SDOI2011】染色

2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MB Submit: 4537  Solved: 1702 [Submit][Status][Discuss] Description 给定一棵有n个节点的无根树和m个操作,操作有2类: 1.将节点a到节点b路径上全部点都染成颜色c: 2.询问节点a到节点b路径上的颜色段数量(连续同样颜色被觉得是同一段).如"112221"由3段组成:"11".&quo