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

ydc的博客

 
 
 

日志

 
 

bzoj 1036(树链剖分)  

2013-10-02 15:42:52|  分类: 模板 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
重新写这道题,练习树链剖分
为qtree4 & bzoj上的xmatree打伏笔
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define it tree[root]
#define lson tree[root<<1]
#define rson tree[root<<1|1]
#define maxn 30010
using namespace std;
struct Seg_tree
{
int sum,maxv;
friend Seg_tree operator + (const Seg_tree &a,const Seg_tree &b)
{
static Seg_tree c;
c.sum=a.sum+b.sum;
c.maxv=max(a.maxv,b.maxv);
return c;
}
}tree[maxn<<2];
vector<int> to[maxn];
int n,tot,val[maxn];
int dep[maxn],father[maxn],size[maxn],son[maxn],id[maxn],top[maxn];
void read()
{
scanf("%d",&n);
for(int i=2,a,b;i<=n;++i)
{
scanf("%d %d",&a,&b);
to[a].push_back(b),to[b].push_back(a);
}
for(int i=1;i<=n;++i)
scanf("%d",&val[i]);
}
void DFS(int p)
{
size[p]=1;
for(vector<int>::iterator e=to[p].begin();e!=to[p].end();++e)
if(father[p]!=*e)
{
father[*e]=p,dep[*e]=dep[p]+1;
DFS(*e);
size[p]+=size[*e];
if(size[son[p]]<size[*e])
son[p]=*e;
}
}
void Build(int p,int v)
{
id[p]=++tot,top[p]=v;
if(son[p])
Build(son[p],v);
for(vector<int>::iterator e=to[p].begin();e!=to[p].end();++e)
if(father[p]!=*e&&son[p]!=*e)
Build(*e,*e);
}
void Build(int root,int l,int r,int *num)
{
if(l==r)
{
it.sum=it.maxv=val[num[l]];
return ;
}
int mid=(l+r)>>1;
Build(root<<1,l,mid,num),Build(root<<1|1,mid+1,r,num);
it=lson+rson;
}
void Modify(int root,int l,int r,int x,int v)
{
if(l==r)
{
it.sum=it.maxv=v;
return ;
}
int mid=(l+r)>>1;
if(x<=mid)
Modify(root<<1,l,mid,x,v);
else
Modify(root<<1|1,mid+1,r,x,v);
it=lson+rson;
}
Seg_tree Query(int root,int l,int r,int x,int y)
{
if(l==x&&r==y)
return it;
int mid=(l+r)>>1;
if(y<=mid)
return Query(root<<1,l,mid,x,y);
else if(mid<x)
return Query(root<<1|1,mid+1,r,x,y);
else
return Query(root<<1,l,mid,x,mid)+Query(root<<1|1,mid+1,r,mid+1,y);
}
Seg_tree Query(int a,int b)
{
int fa=top[a],fb=top[b];
Seg_tree ans;
ans.maxv=-1<<30,ans.sum=0;
while(fa!=fb)
{
if(dep[fa]<dep[fb])
swap(fa,fb),swap(a,b);
ans=ans+Query(1,1,n,id[fa],id[a]);
a=father[fa],fa=top[a];
}
if(dep[a]>dep[b])
swap(a,b);
ans=ans+Query(1,1,n,id[a],id[b]);
return ans;
}
void Query()
{
static int num[maxn];
for(int i=1;i<=n;++i)
num[id[i]]=i;
Build(1,1,n,num);
int m;
scanf("%d",&m);
char task[10];
for(int i=1,a,b;i<=m;++i)
{
scanf("%s %d %d",task+1,&a,&b);
if(task[1]=='C')
Modify(1,1,n,id[a],b);
else
{
Seg_tree ans=Query(a,b);
if(task[2]=='S')
printf("%d\n",ans.sum);
else
printf("%d\n",ans.maxv);
}
}
}
int main()
{
freopen("1036.in","r",stdin);
freopen("1036.out","w",stdout);
read();
DFS(1);
Build(1,1);
Query();
fclose(stdin);
fclose(stdout);
return 0;
}


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

历史上的今天

评论

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

页脚

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