脚本宝典收集整理的这篇文章主要介绍了hdu4348 To the moon (可持久化线段树)，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4348
题目大意：给定含有n个数的序列，有以下四种操作
1.C l r d:表示对区间[l,r]中的数加上d，并且时间加1
2.Q l r：询问当前时间区间[l,r]的和
3.H l r t:询问时间t区间[l,r]的和
4.B t :时间回到t
Sample Input
解题思路：用线段树求区间和时可以不用把lazy标记下传，因为每次都下传的话消耗的空间会很大，很可能爆内存，我们可以直接在询问时，把当前区间的懒惰标记用一个参数传下去，然后找到要求和的区间时，直接把从上到下的懒惰标记累加和乘以区间长度再加上这段区间原本的和就可以了。
代码：
#include<bITs/stdc++.h> using namespace std; tyPEdef long long ll; const int maxn=1e5+7; struct node{ int l,r; ll lazy,sum; }tree[maxn*30]; int n,m,t,cnt,root[maxn]; void pushup(int rt,int l,int r){ tree[rt].sum=tree[tree[rt].l].sum+tree[tree[rt].r].sum+tree[rt].lazy*(r-l+1); } void build(int &rt,int r){ rt=++cnt; tree[rt].lazy=0; if(l==r){ scanf("%lld",&tree[rt].sum); return; } int mid=(l+r)/2; build(tree[rt].l,l,mid); build(tree[rt].r,mid+1,r); pushup(rt,r); } void update(int &Now,int PRe,int L,int R,int val,int r){ Now=++cnt,tree[Now]=tree[pre]; if(L<=l&&R>=r){ tree[Now].sum+=1ll*(r-l+1)*val; tree[Now].lazy+=val; return; } int mid=(l+r)/2; if(L<=mid) update(tree[Now].l,tree[pre].l,L,R,val,mid); if(R>;mid) update(tree[Now].r,tree[pre].r,mid+1,r); pushup(Now,r); } ll query(int Now,int lazy,int r){ if(L<=l&&R>=r){ return tree[Now].sum+1ll*(r-l+1)*lazy; } int mid=(l+r)/2; ll res=0; lazy+=tree[Now].lazy; if(mid>=L) res+=query(tree[Now].l,lazy,mid); if(mid<R) res+=query(tree[Now].r,r); return res; } int main(){ char op[10]; scanf("%d%d",&n,&m); build(root[0],1,n); int l,r,T; t=0; while(m--){ scanf("%s",op); if(op[0]==‘C‘){ scanf("%d%d%d",&l,&r,&val); t++; update(root[t],root[t-1],n); }else if(op[0]==‘Q‘){ scanf("%d%d",&r); printf("%lld\n",query(root[t],0,n)); }else if(op[0]==‘H‘){ scanf("%d%d%d",&T); printf("%lld\n",query(root[T],n)); }else if(op[0]==‘B‘){ scanf("%d",&t); } } return 0; }
以上是脚本宝典为你收集整理的hdu4348 To the moon (可持久化线段树)全部内容，希望文章能够帮你解决hdu4348 To the moon (可持久化线段树)所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。