首页 > 代码库 > BZOJ 1036 树链剖分模板题
BZOJ 1036 树链剖分模板题
BZOJ 1036
题意:一棵树,每个点有权值,三种操作:修改一个点的值;询问一条链上最大值;询问一条链上权值和。
tags:模板题
// bzoj 1036#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define FF(i,a,b) for (int i=a;i<=b;i++)#define F(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3ftypedef long long ll;const int N = 3e4+10;struct Edge{int to, next;}e[N];struct Point{int mx, sum;}t[N<<2];int n, sz, Size[N], dep[N], w[N], head[N], pos[N], tot, bl[N], fa[N];void Addedge(int u, int v) { e[tot].to=v, e[tot].next=head[u], head[u]=tot++; }void Init(){ mes(head,-1); scanf("%d", &n); int u, v; FF(i,1,n-1) { scanf("%d %d", &u, &v); Addedge(u, v); Addedge(v, u); }}void dfs1(int u) //搜索出各个子树的Size{ Size[u]=1; for(int i=head[u]; i!=-1; i=e[i].next) if(e[i].to!=fa[u]) { int v=e[i].to; fa[v]=u, dep[v]=dep[u]+1; dfs1(v); Size[u]+=Size[v]; }}void dfs2(int u, int chain) //构建树链{ sz++, pos[u]=sz, bl[u]=chain; //pos[]分配u结点在线段树中的编号,chain是一条链上头结点的标号 int mx=0; for(int i=head[u]; i!=-1; i=e[i].next) { int v=e[i].to; if(dep[v]>dep[u] && Size[v]>Size[mx]) mx=v; } if(mx==0) return ; dfs2(mx, chain); for(int i=head[u]; i!=-1; i=e[i].next) { int v=e[i].to; if(dep[v]>dep[u] && mx!=v) dfs2(v, v); }}void update(int ro, int l, int r, int x, int y) //线段树单点更新{ if(l==r) { t[ro].mx=t[ro].sum=y; return ; } int mid=(l+r)>>1; if(x<=mid) update(ro<<1, l, mid, x, y); else update(ro<<1|1, mid+1, r, x, y); t[ro].mx=max(t[ro<<1].mx, t[ro<<1|1].mx); t[ro].sum=t[ro<<1].sum+t[ro<<1|1].sum;}int querymx(int ro, int l, int r, int x, int y) //线段树区间求最大值{ if(l==x && r==y) return t[ro].mx; int mid=(l+r)>>1; if(y<=mid) return querymx(ro<<1, l, mid, x, y); else if(mid<x) return querymx(ro<<1|1, mid+1, r, x, y); else return max(querymx(ro<<1, l, mid, x, mid), querymx(ro<<1|1, mid+1, r, mid+1, y));}int solvemx(int x, int y){ int mx=-INF; while(bl[x]!=bl[y]) { if(dep[bl[x]]<dep[bl[y]]) swap(x, y); mx=max(mx, querymx(1, 1, sz, pos[bl[x]], pos[x])); x=fa[bl[x]]; } if(pos[x]>pos[y]) swap(x, y); mx=max(mx, querymx(1, 1, sz, pos[x], pos[y])); return mx;}int querysum(int ro, int l, int r, int x, int y) //线段树区间求和{ if(l==x && r==y) return t[ro].sum; int mid=(l+r)>>1; if(y<=mid) return querysum(ro<<1, l, mid, x, y); else if(mid<x) return querysum(ro<<1|1, mid+1, r, x, y); else return querysum(ro<<1, l, mid, x, mid)+querysum(ro<<1|1, mid+1, r, mid+1, y);}int solvesum(int x, int y){ int sum=0; while(bl[x]!=bl[y]) { //不在一条重链上时,就一边修改,一边往同一条重链上靠 if(dep[bl[x]]<dep[bl[y]]) swap(x, y); sum+=querysum(1, 1, sz, pos[bl[x]], pos[x]); x=fa[bl[x]]; } if(pos[x]>pos[y]) swap(x, y); sum+=querysum(1, 1, sz, pos[x], pos[y]); return sum;}void solve(){ FF(i,1,n) scanf("%d", &w[i]), update(1, 1, sz, pos[i], w[i]); int q, x, y; char str[10]; scanf("%d", &q); FF(i,1,q) { scanf("%s %d %d", str, &x, &y); if(str[0]==‘C‘) w[x]=y, update(1, 1, sz, pos[x], y); else if(str[1]==‘M‘) printf("%d\n", solvemx(x, y)); else printf("%d\n", solvesum(x, y)); }}int main(){ Init(); dfs1(1); dfs2(1, 1); solve(); return 0;}
BZOJ 1036 树链剖分模板题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。