注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2243][SDOI2011]染色  

2015-06-20 15:17:33|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2243: [SDOI2011]染色

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 3271  Solved: 1262
[Submit][Status][Discuss]

Description

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

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

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

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

Input

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

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

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

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

“C a b c”表示这是一个染色操作,把节点a到节点b路径上所有点(包括ab)都染成颜色c

“Q a b”表示这是一个询问操作,询问节点a到节点b(包括ab)路径上的颜色段数量。

Output

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

Sample Input

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

Sample Output

3
1
2

HINT

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

Source

Solution

本来想练习树链剖分的,然而想了想,还是写了LCT。毕竟短啊
维护信息的时候,记录一下当前区间内的最左端颜色L、最右端颜色R、颜色总数sum。
sum[o]=sum[o<<1]+sum[o<<1|1]-(R[o<<1]==L[o<<1|1])

Code

/**************************************************************
    Problem: 2243
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:10256 ms
    Memory:4744 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
char ch,B[1<<15],*S=B,*T=B,op;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 100010
int n,m,i,x,y,rev[N],siz[N],son[N][2],fa[N],col[N],add[N],L[N],R[N],sum[N],st;
#define nr(t) (son[fa[t]][0]==t||son[fa[t]][1]==t)
#define ls son[t][0]
#define rs son[t][1]
#define swap(x,y) (st=x,x=y,y=st)
void pu(int t){
    sum[t]=1,L[t]=R[t]=col[t];
    if(ls)L[t]=L[ls],sum[t]+=sum[ls]-(col[t]==R[ls]);
    if(rs)R[t]=R[rs],sum[t]+=sum[rs]-(col[t]==L[rs]);
}
void rtt(int t){
    int f=fa[t],p=son[f][1]==t;
    fa[t]=fa[f],nr(f)?son[fa[f]][son[fa[f]][1]==f]=t:1,
    (son[f][p]=son[t][!p])?fa[son[f][p]]=f:1,
    pu(son[fa[f]=t][!p]=f);
}
void pv(int t){
    if(nr(t))pv(fa[t]);
    if(rev[t])rev[t]=0,rev[ls]^=1,rev[rs]^=1,swap(L[ls],R[ls]),swap(L[rs],R[rs]),swap(ls,rs);
    if(add[t]!=-1)add[ls]=add[rs]=col[ls]=col[rs]=add[t],L[ls]=L[rs]=R[ls]=R[rs]=add[t],sum[ls]=sum[rs]=1,add[t]=-1;
}
void splay(int t){int f;
    for(pv(t);nr(t);rtt(t))
    if(f=fa[t],nr(f))rtt(son[f][1]==t^son[fa[f]][1]==f?t:f);
    pu(t);
}
void access(int t){
    for(int las=0;t;splay(t),rs=las,las=t,t=fa[t]);
}
#define mkr(t) (access(t),splay(t),rev[t]^=1)
#define link(x,y) (mkr(x),fa[x]=y)
#define cut(x,y) (mkr(x),access(y),splay(y),fa[x]=son[y][0]=0)
int main(){
    memset(add,-1,sizeof(add));
    for(n=F(),m=F(),i=1;i<=n;i++)L[i]=R[i]=col[i]=F();
    for(i=1;i<n;i++)x=F(),y=F(),link(x,y);
    for(;m--;){
        while(op=getc(),op!='C'&&op!='Q');
        x=F(),y=F(),mkr(x),access(y),splay(y);
        if(op=='C')L[y]=R[y]=add[y]=col[y]=F(),sum[y]=1;
        else printf("%d\n",sum[y]);
    }
}
  评论这张
 
阅读(21)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018