bzoj 2243 染色树链剖分好题！ - c++编程基础

TOP

bzoj 2243 染色树链剖分好题！

2015-07-20 17:24:11 来源: 作者: 【大中小】浏览:1次

Tags：bzoj 2243 染色好题

题意：中文题。

思路：很好的一道树链剖分。树剖后，线段树要记录左端点l,右端点r，左端点的颜色lc,右端点的颜色rc,区间成段更新的标记tag,区间

有多少颜色段。区间合并的时候要注意如果左子树的右端和右子树的左端颜色相同那么数量要减一。但是存在一个问题当前剖到

的链与上一次的链在相交的边缘可能颜色相同，如果颜色相同答案需要减一。所以统计答案的时候要记录下上一次剖到的链的左端

点的颜色，与当前剖到的链右端点的颜色（因为在处理出的线段树中越靠近根的点位置越左），比较这两个颜色，若相同则答案减

1。又由于有u和v两个位置在向上走，那么要记录ans1，ans2两个变量来存“上一次的左端点颜色”。有一点需要注意，当

top[u]=top[v]的时候，即已经在同一个重链上时，两边端点颜色都要考虑与对应ans比较颜色，相同答案要相应减一。详见代码：

/*********************************************************
  file name: bzoj2243.cpp
  author : kereo
  create time:  2015年01月23日 星期五 09时51分17秒
*********************************************************/
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              using namespace std; typedef long long ll; const int sigma_size=26; const int N=100+50; const int MAXN=100000+50; const int inf=0x3fffffff; const double eps=1e-8; const int mod=100000000+7; #define L(x) (x<<1) #define R(x) (x<<1|1) #define PII pair
             
               #define mk(x,y) make_pair((x),(y)) int n,m,edge_cnt,cnt,Lc,Rc; char str[N]; int col[MAXN],head[MAXN],sz[MAXN],dep[MAXN],fa[MAXN],son[MAXN],top[MAXN],pos[MAXN]; struct Edge{ int u,v,next; }edge[MAXN<<1]; struct node{ int l,r; int num,tag,lc,rc; }segtree[MAXN<<2]; void init(){ edge_cnt=cnt=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v){ edge[edge_cnt].u=u; edge[edge_cnt].v=v; edge[edge_cnt].next=head[u]; head[u]=edge_cnt++; } void dfs1(int u,int pre,int depth){ sz[u]=1; fa[u]=pre; son[u]=0; dep[u]=depth; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v == pre) continue; dfs1(v,u,depth+1); sz[u]+=sz[v]; if(sz[son[u]]
              
               >1; build(L(rt),l,mid); build(R(rt),mid+1,r); } void update(int rt,int l,int r,int x){ if(segtree[rt].l == l && segtree[rt].r == r){ segtree[rt].num=segtree[rt].tag=1; segtree[rt].lc=segtree[rt].rc=x; return ; } push_down(rt); int mid=(segtree[rt].l+segtree[rt].r)>>1; if(r<=mid) update(L(rt),l,r,x); else if(l>mid) update(R(rt),l,r,x); else { update(L(rt),l,mid,x); update(R(rt),mid+1,r,x); } push_up(rt); } int query(int rt,int l,int r,int L,int R){ if(segtree[rt].l == L) Lc=segtree[rt].lc; if(segtree[rt].r == R) Rc=segtree[rt].rc; if(segtree[rt].l == l && segtree[rt].r == r) return segtree[rt].num; push_down(rt); int mid=(segtree[rt].l+segtree[rt].r)>>1; if(r<=mid) return query(L(rt),l,r,L,R); else if(l>mid) return query(R(rt),l,r,L,R); else{ int ans=query(L(rt),l,mid,L,R)+query(R(rt),mid+1,r,L,R); if(segtree[L(rt)].rc == segtree[R(rt)].lc) ans--; return ans; } push_up(rt); } int solve(int u,int v,int id,int c){ int ans=0; if(id == 1){ while(top[u]!=top[v]){ if(dep[top[u]]
               
                dep[v]) swap(u,v); update(1,pos[u],pos[v],c); } else{ //printf("u=%d v=%d pos[u]=%d pos[v]=%d\n",u,v,pos[u],pos[v]); int ans1=-1,ans2=-1; //记录上次链的左端的颜色 while(top[u]!=top[v]){ if(dep[top[u]]
                
                 printf("%d %d\n",son[1],son[2]); /*for(int i=1;i<=n;i++) printf("top[i]=%d pos[i]%d\n",top[i],pos[i]); printf("---------------------------------------\n"); printf("\n");*/ for(int i=1;i<=n;i++) update(1,pos[i],pos[i],col[i]); while(m--){ scanf("%s",str); int u,v; if(str[0] == 'C'){ int c; scanf("%d%d%d",&u,&v,&c); solve(u,v,1,c); } else{ int u,v; scanf("%d%d",&u,&v); printf("%d\n",solve(u,v,2,0)); //printf("--------------------------------------\n"); } } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：CF507E――Breaking Good(BFS,DP)	下一篇：hdu5163---Taking Bus

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: