线段树+lazy-poj3468-A Simple Problem with Integers-CSDN博客

本文链接：https://blog.csdn.net/struct_liao/article/details/54766914

这道题贼坑爹，change的时候也要pushdown，不然回溯的时候会有问题。

#include<stdio.h>
#include<stdlib.h>
#define lld long long
lld ans,a[100010];
int z;
struct node{
    int l,r;
    lld s,s1;
}tree[1000010];
void pushdown(int l,int r,int d){
    if(tree[d].s1!=0){
        if(tree[d<<1].l!=0){
            tree[d<<1].s1+=tree[d].s1;
            tree[d<<1].s+=(lld)tree[d].s1*(tree[d<<1].r-tree[d<<1].l+1);
        }
        if(tree[d<<1|1].l!=0){
            tree[d<<1|1].s1+=tree[d].s1;
            tree[d<<1|1].s+=(lld)tree[d].s1*(tree[d<<1|1].r-tree[d<<1|1].l+1);
        }
        tree[d].s1=0;
    }
}
void home(int l,int r,int d){
    tree[d].s1=0;
    tree[d].l=l;
    tree[d].r=r;
    if(l==r){
        tree[d].s=a[l];
        return;
    }
    int mid=(l+r)>>1;
    home(l,mid,d<<1);
    home(mid+1,r,d<<1|1);
    tree[d].s=tree[d<<1].s+tree[d<<1|1].s;
    return;
}
void find(int l,int r,int d){
    pushdown(l,r,d);
    if(tree[d].l>=l && tree[d].r<=r){
        ans+=tree[d].s;
        return;
    }
    int mid=(tree[d].l+tree[d].r)>>1;
    if(l<=mid)
        find(l,r,d<<1);
    if(r>mid)
        find(l,r,d<<1|1);
    return;
}
void change(int l,int r,int d){
    pushdown(l,r,d);
    if(tree[d].l>=l && tree[d].r<=r){
        tree[d].s1+=z;
        tree[d].s+=(lld)z*(tree[d].r-tree[d].l+1);
        return;
    }
    int mid=(tree[d].l+tree[d].r)>>1;
    if(l<=mid)
        change(l,r,d<<1);
    if(r>mid)
        change(l,r,d<<1|1);
    tree[d].s=tree[d<<1].s+tree[d<<1|1].s;
    return;
}

int main(){
    int n,i,m,x,y;
    char c[10];
      scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        home(1,n,1);
        for(i=1;i<=m;i++){
            scanf("%s",c);
            if(c[0]=='Q'){
                ans=0;
                scanf("%d%d",&x,&y);
                find(x,y,1);
                printf("%lld\n",ans);
            }
            else{
                scanf("%d%d%d",&x,&y,&z);
                change(x,y,1);
            }
        }
    return 0;
}