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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

BZOJ1036(树链剖分模板)  

2014-06-29 22:14:23|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

相比与LCT,树链剖分真是太好理解了。看了一遍这个人的博客就懂了;见推荐阅读

写得太好已无力吐槽,保证你们看完就懂了:

然后上代码,两个dfs建立sizetopidfid等。然后线段树。裸的维护树上路径的最大值、和、还有单点修改,完全就是线段树了。如果真的理解了30分钟码完1A,超开心。代码无缩行120;由于博客无法贴太多代码,故将int main给删了。

#include<cstdio>
#include<algorithm>
#define INF 200000000
#define nn 40010
using namespace std;
struct node{int end,next;}g[nn*2];
struct work{int sum,ma;}tree[nn*5];
int tot,N,id[nn],top[nn],fid[nn],s[nn],f[nn],vis[nn],size[nn],heavy[nn];
int fa[nn],dep[nn],x,y,n,flag,ans,i,Q;
char c[8];
 
void add(int a,int b)
 {g[++tot].end=b;
  g[tot].next=f[a];f[a]=tot;
 }
  
void dfs1(int w)
 {int i,u;
  vis[w]=1;size[w]=1;
  for (i=f[w];i;i=g[i].next)
           {u=g[i].end;
            if (vis[u])continue;
            fa[u]=w;dep[u]=dep[w]+1;
            dfs1(u);
            size[w]+=size[u];
            if (size[heavy[w]]<size[u])
                 heavy[w]=u;
           }
 }
  
void dfs2(int w)
 {int i,u;
  id[w]=++N;fid[N]=w;
  vis[w]=1;
  if (!top[w])top[w]=w;
  if (heavy[w]){top[heavy[w]]=top[w];
                dfs2(heavy[w]);}
  for (i=f[w];i;i=g[i].next)
             {u=g[i].end;
              if (vis[u])continue;
              dfs2(u);
             }
 }
  
void up(int w)
 {tree[w].sum=tree[w*2].sum+tree[w*2+1].sum;
  tree[w].ma=max(tree[w*2].ma,tree[w*2+1].ma);
 }
  
void build_tree(int w,int l,int r)
 {if (l==r){tree[w].sum=tree[w].ma=s[fid[l]]; 
            return;}
 int mid=(l+r)>>1;
 build_tree(w*2,l,mid);build_tree(w*2+1,mid+1,r);
 up(w);
 }
  
void change(int w,int l,int r,int p)
 {if (l==r){tree[w].sum=tree[w].ma=y;
            return;}
 int mid=(l+r)>>1;
 if (p>mid)change(w*2+1,mid+1,r,p);else
           change(w*2,l,mid,p);
 up(w);
 }
  
void q(int w,int l,int r,int ll,int rr)
 {if (l==ll&&r==rr){if (flag==1)
                    ans=max(ans,tree[w].ma);else
                    ans+=tree[w].sum;
                    return;
                   }
 int mid=(l+r)>>1;
 if (rr<=mid)q(w*2,l,mid,ll,rr);else
 if (ll>mid)q(w*2+1,mid+1,r,ll,rr);else
         {q(w*2,l,mid,ll,mid);
          q(w*2+1,mid+1,r,mid+1,rr);
         }
 }
  
int qmax(int x,int y)
 {ans=-INF;flag=1;
 while (top[x]!=top[y])
                 {if (dep[top[x]]<dep[top[y]])swap(x,y);
                  q(1,1,N,id[top[x]],id[x]);
                 x=fa[top[x]];
                 }
 if (dep[x]>dep[y])swap(x,y);
 q(1,1,N,id[x],id[y]);
 return ans;
 }
  
int qsum(int x,int y)
 {ans=0;flag=2;
 while (top[x]!=top[y])
                 {if (dep[top[x]]<dep[top[y]])swap(x,y);
                 q(1,1,N,id[top[x]],id[x]);
                 x=fa[top[x]];
                 }
 if (dep[x]>dep[y])swap(x,y);
 q(1,1,N,id[x],id[y]);
 return ans;
 }
  评论这张
 
阅读(3381)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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