HDU3966 Aragorn's Story(树链剖分)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了HDU3966 Aragorn's Story(树链剖分),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3518字,纯文字阅读大概需要6分钟。
内容图文
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3966
昨天学了树剖以后感觉这个算法非常厉害,于是百度了几个树剖(入门)题来做,这题也是一个树剖入门题啦!
题意:输入n个点,m条边(m一定等于n-1,也不知道为什么还要输入),q个询问。然后输入n个点的权值,然后输入m条边。询问有3种操作:
(1)’I’:[a,b]区间加上c。
(2)’D’:[a,b]区间减去c。
(3)’Q’:查询点x的权值。
所以就是一个树剖套上区间更新的线段树模板。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <ctime>
using
namespace
std;
typedeflonglong LL;
typedef pair<int,int> pii;
#define PB push_back#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define calm (l+r)>>1constint INF=1e9+7;
constint maxn=50010;
struct EE{
int to,next;
EE(){}
EE(int to,int next):to(to),next(next){}
}edge[maxn*2];
int n,m,q,Ecnt,tot,head[maxn];
int val[maxn],deep[maxn],top[maxn],id[maxn],rev[maxn],num[maxn],son[maxn],fa[maxn];
inlinevoid addedge(int a,int b){
edge[Ecnt]=EE(b,head[a]);
head[a]=Ecnt++;
}
void dfs1(int s,int pre,int d){
deep[s]=d;fa[s]=pre;num[s]=1;son[s]=-1;
for(int i=head[s];~i;i=edge[i].next){
int t=edge[i].to;
if(t==pre)continue;
dfs1(t,s,d+1);num[s]+=num[t];
if(son[s]==-1||num[t]>num[son[s]]){
son[s]=t;
}
}
}
void dfs2(int s,int rt){
top[s]=rt;id[s]=++tot;rev[tot]=s;
if(son[s]==-1)return;
dfs2(son[s],rt);
for(int i=head[s];~i;i=edge[i].next){
int t=edge[i].to;
if(t==fa[s]||t==son[s])continue;
dfs2(t,t);
}
}
//SegmentTreestruct node{
int tag,val;
}tree[maxn<<2];
inlinevoid pushdown(int rt,int len){
if(tree[rt].tag){
tree[rt<<1].tag+=tree[rt].tag;
tree[rt<<1|1].tag+=tree[rt].tag;
tree[rt<<1].val+=(len-len/2)*tree[rt].tag;
tree[rt<<1|1].val+=(len/2)*tree[rt].tag;
tree[rt].tag=0;
}
}
void build(int l,int r,int rt){
tree[rt].tag=tree[rt].val=0;
if(l==r){
tree[rt].val=val[rev[l]];
return;
}
int m=calm;
build(lson);build(rson);
}
void update(int L,int R,int v,int l,int r,int rt){
if(L<=l&&r<=R){
tree[rt].tag+=v;
tree[rt].val+=(r-l+1)*v;
return;
}
pushdown(rt,r-l+1);
int m=calm;
if(L<=m)update(L,R,v,lson);
if(R>m)update(L,R,v,rson);
}
int query(int x,int l,int r,int rt){
if(l==r){
return tree[rt].val;
}
pushdown(rt,r-l+1);
int m=calm;
if(x<=m)return query(x,lson);
elsereturn query(x,rson);
}
void findadd(int x,int y,int v){
int f1=top[x],f2=top[y];
while(f1!=f2){
if(deep[f1]<deep[f2]){
swap(x,y);swap(f1,f2);
}
update(id[f1],id[x],v,1,n,1);
x=fa[f1];f1=top[x];
}
if(deep[x]>deep[y]){
swap(x,y);
}
update(id[x],id[y],v,1,n,1);
}
int main(){
//freopen("/home/xt/code/acm/input.txt","r",stdin);while(scanf("%d%d%d",&n,&m,&q)!=EOF){
for(int i=1;i<=n;i++){
scanf("%d",&val[i]);
head[i]=-1;
}
Ecnt=0;
for(int i=0;i<m;i++){
int a,b;scanf("%d%d",&a,&b);
addedge(a,b);addedge(b,a);
}
tot=0;
dfs1(1,0,1);dfs2(1,1);
build(1,n,1);
char op[5];
while(q--) {
scanf("%s", op);
if(op[0]==‘I‘){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
findadd(a,b,c);
}
elseif(op[0]==‘D‘){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
findadd(a,b,-c);
}
else{
int x;scanf("%d",&x);
printf("%d\n",query(id[x],1,n,1));
}
}
}
//printf("[Run in %.1fs]\n",(double)clock()/CLOCKS_PER_SEC);return0;
}
(树链剖分)' ref='nofollow'>HDU3966 Aragorn's Story(树链剖分)
原文:http://blog.csdn.net/xtttgo/article/details/51335501
内容总结
以上是互联网集市为您收集整理的HDU3966 Aragorn's Story(树链剖分)全部内容,希望文章能够帮你解决HDU3966 Aragorn's Story(树链剖分)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。