CDOJ 1057 秋实大哥与花线段树区间更新+区间查询

链接：

I - 秋实大哥与花

Time Limit:1000MS Memory Limit:65535KB 64bit IO Format:%lld & %llu

Submit Status Practice UESTC 1057

Appoint description:

Description

秋实大哥是一个儒雅之人，昼听笙歌夜醉眠，若非月下即花前。

所以秋实大哥精心照料了很多花朵。现在所有的花朵排成了一行，每朵花有一个愉悦值。

秋实大哥每天要对着某一段连续的花朵歌唱，然后这些花朵的愉悦值都会增加一个相同的值

同时他想知道每次他唱完歌后这一段连续的花朵的愉悦值总和是多少。

Input

第一行有一个整数

第二行包含

第三行包含一个整数

接下来

Output

输出共

Sample Input

3
0 0 0
3
1 2 1
1 2 -1
1 3 1

Sample Output

2
0
3

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
#define MM(a,b) memset(a,b,sizeof(a));
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const double pi=acos(-1);
const int maxn=100000;
ll ans[maxn+10];
struct Tree{
    ll sum,lazy;
    int l,r;
    void fun(ll v){
        this->lazy+=v;
        sum+=v*(r-l+1);
    }//v  需要改成 long long   否则乘下来爆int
    int mid(){
        return (l+r)>>1;
    }
}tree[4*maxn+10];

void pushdown(int id)
{
    int k=tree[id].lazy;
    if(k==0) return;
    tree[2*id].fun(k);
    tree[2*id+1].fun(k);
    tree[id].lazy=0;
}

void pushup(int id)
{
    tree[id].sum=tree[2*id].sum+tree[2*id+1].sum;
}

void build(int id,int l,int r)
{
    tree[id].l=l;
    tree[id].r=r;
    tree[id].lazy=tree[id].sum=0;

    if(r==l) scanf("%lld",&tree[id].sum);
    else{
        int mid=(l+r)>>1;
        build(2*id,l,mid);
        build(2*id+1,mid+1,r);
        pushup(id);
    }
}

void update(int id,int l,int r,int v)
{
    if(l<=tree[id].l&&tree[id].r<=r)
        tree[id].fun(v);
    else
    {
        int mid=tree[id].mid();
        pushdown(id);
        if(l<=mid) update(2*id,l,r,v);
        if(r>mid) update(2*id+1,l,r,v);
        pushup(id);
    }
}

ll query(int id,int l,int r)
{
     if(l<=tree[id].l&&tree[id].r<=r)
        return tree[id].sum;
     else  {
            pushdown(id);
            int mid=tree[id].mid();
            ll suml=0,sumr=0;
            if(l<=mid) suml=query(2*id,l,r);
            if(r>mid)  sumr=query(2*id+1,l,r);
            pushup(id);
            return suml+sumr;
        }
}

int main()
{
    int n,m;
    while(~scanf("%d",&n))
    {
        build(1,1,n);
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
            {
                int l,r,v;
                scanf("%d %d %d",&l,&r,&v);
                update(1,l,r,v);
                ans[i]=query(1,l,r);
            }
        for(int i=1;i<=m;i++)
            printf("%lld
",ans[i]);
    }
    return 0;
}

　　分析：模板题，，但是fun函数参数需要写成long long 形式，否则爆int

CDOJ 1057 秋实大哥与花 线段树 区间更新+区间查询

CDOJ 1057 秋实大哥与花线段树区间更新+区间查询