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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[SDOI2011]染色  

2014-05-11 11:31:35|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
@[SDOI2011]染色

树链剖分....

昨天刚学的

今天上午又写了一题,结果写调好长时间QAQ

标记各种写挂.....

还有BZOJ挂了好蛋疼...

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100000+1;
int n,m,data[N];
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+'){cc=getchar();fh=1;}
if(cc=='-'){cc=getchar();fh=-1;}
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
struct Point{
int d;
Point *next;
Point(){next=NULL;}
void push(int);
}map[N];
void Point::push(int a){
Point *l;
l=new Point();
l->next=next;
next=l;
l->d=a;
}
int fa[N],deep[N],son[N],size[N];
int bh[N],rebh[N],ROOT,Tn,top[N],cf[N*2];
int lson[N*2],rson[N*2],tree[N*2],lc[N*2],rc[N*2];
void dfs1(int x,int f){
fa[x]=f;size[x]=1;
for(Point *i=map[x].next;i!=NULL;i=i->next)
if(i->d!=f){
deep[i->d]=deep[x]+1;
dfs1(i->d,x);
size[x]+=size[i->d];
if(size[i->d]>size[son[x]])son[x]=i->d;
}
}
void dfs2(int x){
bh[x]=++bh[0];rebh[bh[0]]=x;
if(!son[x]) return;
top[son[x]]=top[x];
dfs2(son[x]);
for(Point *i=map[x].next;i!=NULL;i=i->next)
if(i->d!=fa[x]&&i->d!=son[x]){
top[i->d]=i->d;
dfs2(i->d);
}
}
void update(int ro){
if(lson[ro]){
tree[ro]=tree[lson[ro]]+tree[rson[ro]];
if(rc[lson[ro]]==lc[rson[ro]]) tree[ro]--;
lc[ro]=lc[lson[ro]];
rc[ro]=rc[rson[ro]];
}
}
int Build(int l,int r){
int ro=++Tn,mid;
if(l<r){
mid=(l+r)/2;
lson[ro]=Build(l,mid);
rson[ro]=Build(mid+1,r);
update(ro);
}else lc[ro]=rc[ro]=data[rebh[l]],tree[ro]=1;
return ro;
}
//标记经常写错QAQ*
void pushdown(int ro){
if(cf[ro]!=-1){
if(lson[ro])lc[lson[ro]]=rc[lson[ro]]=cf[lson[ro]]=cf[ro],tree[lson[ro]]=1;
if(rson[ro])lc[rson[ro]]=rc[rson[ro]]=cf[rson[ro]]=cf[ro],tree[rson[ro]]=1;
cf[ro]=-1;
}
}
void set(int ro,int la,int ra,int l,int r,int val){
if(la>ra)swap(la,ra);
pushdown(ro);
if(la<=l&&r<=ra){lc[ro]=rc[ro]=cf[ro]=val;tree[ro]=1;return;}
int mid=(l+r)/2;
if(la<=mid )set(lson[ro],la,ra,l,mid,val);
if(mid+1<=ra)set(rson[ro],la,ra,mid+1,r,val);
update(ro);
}
struct ASK{
int llc,rrc,tr;
ASK(){tr=0;}
ASK(int ll,int rr,int t):llc(ll),rrc(rr),tr(t){}
};
ASK operator + (ASK a,ASK b){
if(!a.tr)return b;if(!b.tr) return a;
ASK c;c.tr=a.tr+b.tr;
if(a.rrc==b.llc) c.tr--;
c.llc=a.llc;c.rrc=b.rrc;
return c;
}
ASK ask(int ro,int la,int ra,int l,int r){
if(la>ra)swap(la,ra);
pushdown(ro);
if(la<=l&&r<=ra) return ASK(lc[ro],rc[ro],tree[ro]);
ASK ll,rr;
int mid=(l+r)/2;
if(la<=mid) ll=ask(lson[ro],la,ra,l,mid);
if(mid+1<=ra) rr=ask(rson[ro],la,ra,mid+1,r);
return ll+rr;
}
//染色0-? 询问 -1 *
int work(int a,int b,int t){
ASK aans,bans,ans;
while(top[a]!=top[b]){
if(deep[top[a]]<deep[top[b]]) {swap(a,b);swap(aans,bans);}
if(t!=-1) set(ROOT,bh[top[a]],bh[a],1,bh[0],t);
else {ans=ask(ROOT,bh[top[a]],bh[a],1,bh[0]);
aans=ans+aans;}
a=fa[top[a]];
}
if(t!=-1) {set(ROOT,bh[a],bh[b],1,bh[0],t);return 0;}
if(bh[a]>bh[b]){swap(a,b);swap(aans,bans);}
ans=ask(ROOT,bh[a],bh[b],1,bh[0]);
swap(aans.llc,aans.rrc);
ans=(aans+ans)+bans;
return ans.tr;
}
int main(){
//freopen("input.txt","r",stdin);
int i,j,a,b;
n=scan();m=scan();
for(i=1;i<=n;i++)
data[i]=scan();
for(i=1;i<n;i++){
a=scan();b=scan();
map[a].push(b);
map[b].push(a);
}
dfs1(1,0);
top[1]=1;
dfs2(1);
ROOT=Build(1,bh[0]);
memset(cf,-1,sizeof(cf));
for(i=1;i<=m;i++){
char cc=' ';
do{cc=getchar();}while(cc==' '||cc=='\r'||cc=='\n');
a=scan();b=scan();
if(cc=='C'){
work(a,b,scan());
}else{
printf("%d\n",work(a,b,-1));
}
}
return 0;
}


  评论这张
 
阅读(39)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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