hdu4348 To the moon (可持久化线段树)

开发技术作者： 2024-06-25 13:20:01

题目链接：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 10 5 1 2 3 4 5

题目链接：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

10 5

1 2 3 4 5 6 7 8 9 10

Q 4 4

Q 1 10

Q 2 4

C 3 6 3

Q 2 4

2 4

0 0

C 1 1 1

C 2 2 -1

Q 1 2

H 1 2 1

Sample Output

4
55
9
15

0
1

解题思路：用线段树求区间和时可以不用把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;
}