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

链接：

I - 秋实大哥与花

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

Submit Status Practice UESTC 1057

Appoint description:
System Crawler (2016-04-19)

Description

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

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

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

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

Input

第一行有一个整数n，表示花朵的总数目。

第二行包含n个整数ai，表示第i朵花初始的愉悦值。

第三行包含一个整数m，表示秋实大哥唱了m天的歌。

接下来m行，每行包含三个整数l r v，表示秋实大哥对着[l,r]这个区间内的花朵歌唱，每朵花的愉悦值增加了v。

1≤n，m，ai，|v|≤100000，1≤l≤r≤n。

Output

输出共m行，第i行表示秋实大哥完成第i天的歌唱后，那一段花朵的愉悦值总和。

Sample Input

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

Sample Output

2
0

#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\n",ans[i]);

    }

    return 0;

}

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

巴特西

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

最新文章

热门文章

巴特西

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

最新文章

热门文章

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