首页 > 代码库 > BZOJ 2157 旅游（树链剖分+线段树）
BZOJ 2157 旅游（树链剖分+线段树）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2157
【题目大意】
支持修改边，链上查询最大值最小值总和，以及链上求相反数
【题解】
树链剖分，然后线段树维护线段操作即可。
【代码】
#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int INF=~0U>>1;const int N=20010,M=N<<2;int a[N];namespace Segment_Tree{ int tot; struct node{int l,r,a,b,rev_tag,min_val,max_val,sum;}T[M]; void build(int,int); void Initialize(int n){ tot=0; build(1,n); } void addtag(int x){ T[x].sum=-T[x].sum; T[x].max_val=-T[x].max_val; T[x].min_val=-T[x].min_val; swap(T[x].min_val,T[x].max_val); T[x].rev_tag^=1; } void pb(int x){ if(T[x].rev_tag){ if(T[x].l)addtag(T[x].l); if(T[x].r)addtag(T[x].r); T[x].rev_tag^=1; } } void up(int x){ T[x].sum=T[T[x].l].sum+T[T[x].r].sum; T[x].max_val=max(T[T[x].l].max_val,T[T[x].r].max_val); T[x].min_val=min(T[T[x].l].min_val,T[T[x].r].min_val); } void build(int l,int r){ int x=++tot; T[x].a=l;T[x].b=r;T[x].rev_tag=T[x].l=T[x].r=0; if(l==r){T[x].sum=T[x].min_val=T[x].max_val=a[l];return;} int mid=(l+r)>>1; T[x].l=tot+1;build(l,mid); T[x].r=tot+1;build(mid+1,r); up(x); } void change(int x,int pos,int p){ if(T[x].a==T[x].b){T[x].sum=T[x].min_val=T[x].max_val=p;return;} if(T[x].rev_tag)pb(x); int mid=(T[x].a+T[x].b)>>1; if(mid>=pos&&T[x].l)change(T[x].l,pos,p); if(mid<pos&&T[x].r)change(T[x].r,pos,p); up(x); } void reverse(int x,int a,int b){ if(a<=T[x].a&&T[x].b<=b){addtag(x);return;} if(T[x].rev_tag)pb(x); int mid=(T[x].a+T[x].b)>>1; if(a<=mid)reverse(T[x].l,a,b); if(b>mid)reverse(T[x].r,a,b); up(x); } int query_sum(int x,int a,int b){ if(a<=T[x].a&&T[x].b<=b)return T[x].sum; if(T[x].rev_tag)pb(x); int mid=(T[x].a+T[x].b)>>1,res=0; if(a<=mid)res+=query_sum(T[x].l,a,b); if(b>mid)res+=query_sum(T[x].r,a,b); return res; } int query_min(int x,int a,int b){ //printf("%d %d %d\n",T[x].min_val,a,b); if(a<=T[x].a&&T[x].b<=b)return T[x].min_val; if(T[x].rev_tag)pb(x); int mid=(T[x].a+T[x].b)>>1,res=INF; if(a<=mid)res=min(res,query_min(T[x].l,a,b)); if(b>mid)res=min(res,query_min(T[x].r,a,b)); return res; } int query_max(int x,int a,int b){ if(a<=T[x].a&&T[x].b<=b)return T[x].max_val; if(T[x].rev_tag)pb(x); int mid=(T[x].a+T[x].b)>>1,res=-INF; if(a<=mid)res=max(res,query_max(T[x].l,a,b)); if(b>mid)res=max(res,query_max(T[x].r,a,b)); return res; }}namespace Tree_Chain_Subdivision{ int ed,root,d[N],v[N<<1],vis[N],f[N],g[N<<1]; int nxt[N<<1],size[N],son[N],st[N],en[N],dfn,top[N]; void add_edge(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;} void dfs(int x){ size[x]=1; for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){ f[v[i]]=x,d[v[i]]=d[x]+1; dfs(v[i]),size[x]+=size[v[i]]; if(size[v[i]]>size[son[x]])son[x]=v[i]; } } void dfs2(int x,int y){ if(x==-1)return; st[x]=++dfn;top[x]=y; if(son[x])dfs2(son[x],y); for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]); en[x]=dfn; } // 查询x,y两点的lca int lca(int x,int y){ for(;top[x]!=top[y];x=f[top[x]])if(d[top[x]]<d[top[y]]){int z=x;x=y;y=z;} return d[x]<d[y]?x:y; } // x是y的祖先，查询x到y方向的第一个点 int lca2(int x,int y){ int t; while(top[x]!=top[y])t=top[y],y=f[top[y]]; return x==y?t:son[x]; } // 对x到y路径上的点取反操作 void reverse(int x,int y){ for(;top[x]!=top[y];x=f[top[x]]){ if(d[top[x]]<d[top[y]]){int z=x;x=y;y=z;} Segment_Tree::reverse(1,st[top[x]],st[x]); }if(d[x]<d[y]){int z=x;x=y;y=z;} Segment_Tree::reverse(1,st[y]+1,st[x]); } // 查询x到y路径上的最小值 int query_min(int x,int y){ int res=INF; for(;top[x]!=top[y];x=f[top[x]]){ if(d[top[x]]<d[top[y]]){int z=x;x=y;y=z;} res=min(res,Segment_Tree::query_min(1,st[top[x]],st[x])); }if(d[x]<d[y]){int z=x;x=y;y=z;} res=min(res,Segment_Tree::query_min(1,st[y]+1,st[x])); return res; } // 查询x到y路径上的最大值 int query_max(int x,int y){ int res=-INF; for(;top[x]!=top[y];x=f[top[x]]){ if(d[top[x]]<d[top[y]]){int z=x;x=y;y=z;} res=max(res,Segment_Tree::query_max(1,st[top[x]],st[x])); }if(d[x]<d[y]){int z=x;x=y;y=z;} res=max(res,Segment_Tree::query_max(1,st[y]+1,st[x])); return res; } // 查询x到y路径上的总和 int query_sum(int x,int y){ int res=0; for(;top[x]!=top[y];x=f[top[x]]){ if(d[top[x]]<d[top[y]]){int z=x;x=y;y=z;} res=res+Segment_Tree::query_sum(1,st[top[x]],st[x]); }if(d[x]<d[y]){int z=x;x=y;y=z;} res=res+Segment_Tree::query_sum(1,st[y]+1,st[x]); return res; } void Initialize(){ memset(g,dfn=ed=0,sizeof(g)); memset(v,0,sizeof(v)); memset(nxt,0,sizeof(nxt)); memset(son,-1,sizeof(son)); }}int n,m,e[N][3];char op[5];int main(){ scanf("%d",&n); using namespace Tree_Chain_Subdivision; Initialize(); for(int i=0;i<n-1;i++){ scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]); e[i][0]++; e[i][1]++; add_edge(e[i][0],e[i][1]); add_edge(e[i][1],e[i][0]); }dfs(1);dfs2(1,1); for(int i=0;i<n-1;i++){ if(d[e[i][0]]>d[e[i][1]])swap(e[i][0],e[i][1]); a[st[e[i][1]]]=e[i][2]; } Segment_Tree::Initialize(n); scanf("%d",&m); while(m--){ scanf("%s",op); if(op[0]==‘C‘){ int x,y; scanf("%d%d",&x,&y); Segment_Tree::change(1,st[e[x-1][1]],y); } else if(op[0]==‘N‘){ int x,y; scanf("%d%d",&x,&y); Tree_Chain_Subdivision::reverse(x+1,y+1); } else if(op[0]==‘S‘){ int x,y; scanf("%d%d",&x,&y); printf("%d\n",Tree_Chain_Subdivision::query_sum(x+1,y+1)); } else if(op[1]==‘I‘){ int x,y; scanf("%d%d",&x,&y); printf("%d\n",Tree_Chain_Subdivision::query_min(x+1,y+1)); } else{ int x,y; scanf("%d%d",&x,&y); printf("%d\n",Tree_Chain_Subdivision::query_max(x+1,y+1)); } }return 0;}BZOJ 2157 旅游（树链剖分+线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。