博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU - 6162(Ch’s gift)
阅读量:4843 次
发布时间:2019-06-11

本文共 3498 字,大约阅读时间需要 11 分钟。

题目()

题目意思:

给定一棵树,树的节点上有权值。接下来会有q次查询。每次查询书上两个节点路径上经过的所有点(包括给出的两个点)权值在[a,b] 这个区间的数求和。每次都是查询这个 s,t,a,b。

解题思路:

按照官方给出的题解,离线+lca。

具体是这样:离线还是要的,我们需要查询s,t这条路径在区间 [a,b] 的数的和。假设 g(x,a,b):代表 树上节点为x的点到根节点这条路径上数字在[a,b] 这个闭区间的数的和。并且假设lca(x,y) 代表x加点与y节点的最近公共祖先。那么每次查询就是:\[g\left ( s,a,b \right )+g(t,a,b)-2*g(lca(s,t),a,b)\]

但是这样计算没有包括lca(s,t)这个点,我们应该特判这个点是否在[a,b]这个区间内部?如果在加上。

所以如何算出需要的g(x,a,b),因为需要的就只有3×q,这么多个。我们发现在遍历这棵树的时候,遍历到一个节点把这个点插入到一个数据结构。遍历完这个点,把这个点删除掉。那么每次遍历到某个点,数据结构里面的点都是这个点到根的所有数字,在这时候我们需要知道数据结构中的数在 [a,b] 这个区间的数字求和是多少?抽象一下,这个数据结构需:

  • 插入一个元素。
  • 删除一个元素。
  • 查询所有元素在[a,b]这个区间的数的和。

我们只需要三个操作。刚好线段树支持这些操作。听说平衡树可以,标程使用 Treap 来维护的。个人线段树用的多,所以就用了线段树。那么线段树节点就维护和,下面有是线段树部分,在结构体封装了。

现在还有 lca,这个的就用倍增随便搞搞。我的处理方法是读入数据,看需要的g(x,a,b)传到树的节点上。遍历树的时候如果有需要的就进行查询操作。

最后输出答案就好,细节可参考本人比较拙的代码。

#include 
#include
#include
#include
#include
#include
#include
#include
using namespace std;typedef long long int LL;const int maxn=1e5+10;struct segtree { struct Node { int lson,rson; LL sum; }T[maxn*32]; int root,sz; int newnode() { sz++; T[sz].lson=T[sz].rson=-1; T[sz].sum=0; return sz; } void init() { sz=-1; root=newnode(); } void insert(int& i,int l,int r,int val) { if(i==-1) i=newnode(); T[i].sum+=val; if(l==r) return ; int mid=(l+r)>>1; if(val<=mid) insert(T[i].lson,l,mid,val); else insert(T[i].rson,mid+1,r,val); } void del(int& i,int l,int r,int val) { if(i==-1) i=newnode(); T[i].sum-=val; if(l==r) return ; int mid=(l+r)>>1; if(val<=mid) del(T[i].lson,l,mid,val); else del(T[i].rson,mid+1,r,val); } LL query(int i,int l,int r,int ql,int qr) { if(i==-1) return 0; if(l==ql&&r==qr) return T[i].sum; int mid=(l+r)>>1; if(qr<=mid) return query(T[i].lson,l,mid,ql,qr); else if(ql>mid) return query(T[i].rson,mid+1,r,ql,qr); else return query(T[i].lson,l,mid,ql,mid)+query(T[i].rson,mid+1,r,mid+1,qr); }}ac;vector
G[maxn];int treeval[maxn],fa[maxn][20],deep[maxn];int n,m;void dfs(int x,int pre){ //printf("dfs x=%d\n",x); fa[x][0]=pre; deep[x]=deep[pre]+1; for(int i=1;i<20;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=0;i<(int)G[x].size();i++) { int to=G[x][i]; if(to==pre) continue; dfs(to,x); }}int lca(int x,int y){ if (deep[x] < deep[y]) { swap(x, y); } int delta = deep[x] - deep[y]; for (int i = 0; i <= 23; ++i) { if ((delta >> i) & 1) { x = fa[x][i]; } } if (x == y) { return x; } for (int i = 19;i>=0; --i) { if (fa[x][i] != fa[y][i]) { x = fa[x][i]; y = fa[y][i]; } } return fa[x][0];}struct Query { LL a,b; LL *p; Query(LL _a,LL _b,LL *_p) { a=_a,b=_b; p=_p; }};struct Answer { LL s,t,lca,temp;}ans[maxn];vector
need[maxn];void df(int x,int pre){ // printf("df x=%d\n",x); ac.insert(ac.root,1,1e9,treeval[x]); for(int i=0;i<(int)need[x].size();i++) { LL *p,a=need[x][i].a,b=need[x][i].b; p=need[x][i].p; LL ans=ac.query(ac.root,1,1e9,a,b); *p=ans; // printf("query x=%d a=%lld b=%lld ans=%lld\n",x,a,b,ans); } for(int i=0;i<(int)G[x].size();i++) { int to=G[x][i]; if(to==pre) continue; df(to,x); } ac.del(ac.root,1,1e9,treeval[x]);}int main(){ while(scanf("%d%d",&n,&m)+1) { for(int i=1;i<=n;i++) { G[i].clear(); need[i].clear(); scanf("%d",&treeval[i]); } for(int i=1;i
=a&&treeval[_lca]<=b) ans[i].temp=treeval[_lca]; else ans[i].temp=0; } ac.init(); df(1,0); for(int i=1;i<=m;i++) { //printf("s=%lld t=%lld lca=%lld\n",ans[i].s,ans[i].t,ans[i].lca); LL ff=ans[i].s+ans[i].t-2*ans[i].lca+ans[i].temp; printf(i==m?"%I64d\n":"%I64d ",ff); } } return 0;}

转载于:https://www.cnblogs.com/coded-ream/p/7502034.html

你可能感兴趣的文章
关于dubbo+shiro导致dubbo无法注入到Realm的问题解决方案
查看>>
Solr添加paoding分词器
查看>>
charles 抓包 (一)
查看>>
隐藏电池栏,遮罩层
查看>>
ES6学习之Iterator和For...of循环
查看>>
css 在各种浏览器兼容调整
查看>>
三元环、四元环计数
查看>>
SpringBoot
查看>>
【mark】linux查看端口占用
查看>>
String的trim()用于去掉字符串前后的空格
查看>>
jquery相关代码
查看>>
USACO 2.3 Zero Sum
查看>>
android 工具类 DateUtil
查看>>
EM算法原理
查看>>
高速排序算法
查看>>
EJB究竟是什么,真的那么神奇吗??
查看>>
数据结构——集合有关
查看>>
NSCondition
查看>>
常用单词7
查看>>
html5中input的type类型有哪些(总结)
查看>>