POJ.3468 A Simple Problem with Integers（线段树 区间更新 区间查询）

题意分析

注意一下懒惰标记，数据部分和更新时的数字都要是long long ，别的没什么大坑。

代码总览

#include <cstdio>

#include <cstring>

#include <algorithm>

#define nmax 200000

using namespace std;

struct Tree{

    int l,r;

    long long val;

    long long  lazy;

    int mid(){

        return (l+r)>>1;

    }

};

Tree tree[nmax<<2];

long long  num[nmax];

void PushUp(int rt)

{

    tree[rt].val = tree[rt<<1].val + tree[rt<<1|1].val;

}

void PushDown(int rt)

{

    if(tree[rt].lazy){

        tree[rt<<1].lazy += tree[rt].lazy;

        tree[rt<<1|1].lazy += tree[rt].lazy;

        tree[rt<<1].val += tree[rt].lazy * (tree[rt<<1].r - tree[rt<<1].l +1) ;

        tree[rt<<1|1].val +=tree[rt].lazy * (tree[rt<<1|1].r - tree[rt<<1|1].l +1);

        tree[rt].lazy = 0;

    }

}

void Build(int l, int r, int rt)

{

    tree[rt].l = l; tree[rt].r = r;

    tree[rt].val = tree[rt].lazy = 0;

    if(l == r){

        tree[rt].val = num[l];

        return;

    }

    Build(l,tree[rt].mid(),rt<<1);

    Build(tree[rt].mid()+1,r,rt<<1|1);

    PushUp(rt);

}

void UpdatePoint(long long  val, int pos, int rt)

{

    if(tree[rt].l == tree[rt].r){

        tree[rt].val+=val;

        return;

    }

    PushDown(rt);

    if(pos<= tree[rt].mid()) UpdatePoint(val,pos,rt<<1);

    else UpdatePoint(val,pos,rt<<1|1);

    PushUp(rt);

}

void UpdateInterval(long long val, int l, int r, int rt)

{

    if(tree[rt].l >r || tree[rt].r < l) return;

    if(tree[rt].l >= l && tree[rt].r <= r){

        tree[rt].val += val * (tree[rt].r - tree[rt].l + 1);

        tree[rt].lazy += val;

        return;

    }

    PushDown(rt);

    UpdateInterval(val,l,r,rt<<1) ;

    UpdateInterval(val,l,r,rt<<1|1);

    PushUp(rt);

}

long long Query(int l,int r,int rt)

{

    if(l>tree[rt].r || r<tree[rt].l) return 0;

    PushDown(rt);

    if(l <= tree[rt].l && tree[rt].r <= r) return tree[rt].val;

    else return Query(l,r,rt<<1) + Query(l,r,rt<<1|1);

}

int N,Q,a,b;

long long c;

char op;

int main()

{

    //freopen("in3468.txt","r",stdin);

    while(scanf("%d %d",&N,&Q) != EOF){

        for(int i = 1;i<=N;++i) scanf("%I64d",&num[i]);

        Build(1,N,1);

        for(int i = 0;i<Q;++i){

            scanf(" %c %d %d",&op,&a,&b);

            if(op == 'C'){

                scanf("%I64d",&c);

                UpdateInterval(c,a,b,1);

            }else{

                printf("%I64d\n",Query(a,b,1));

            }

        }

    }

    return 0;

}