天天看點

CDOJ-1057 秋實大哥與花(線段樹區間更新) 秋實大哥與花

秋實大哥與花

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit   Status

秋實大哥是一個儒雅之人,晝聽笙歌夜醉眠,若非月下即花前。

是以秋實大哥精心照料了很多花朵。現在所有的花朵排成了一行,每朵花有一個愉悅值。

秋實大哥每天要對着某一段連續的花朵歌唱,然後這些花朵的愉悅值都會增加一個相同的值 v v( v v可能為負)。

同時他想知道每次他唱完歌後這一段連續的花朵的愉悅值總和是多少。

Input

第一行有一個整數 n n,表示花朵的總數目。

第二行包含 n n個整數 ai ai,表示第 i i朵花初始的愉悅值。

第三行包含一個整數 m m,表示秋實大哥唱了 m m天的歌。

接下來 m m行,每行包含三個整數 l l  r r  v v,表示秋實大哥對着 [l,r] [l,r]這個區間内的花朵歌唱,每朵花的愉悅值增加了 v v。

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

Output

輸出共 m m行,第 i i行表示秋實大哥完成第 i i天的歌唱後,那一段花朵的愉悅值總和。

Sample input and output

Sample Input Sample Output
3
0 0 0
3
1 2 1
1 2 -1
1 3 1      
2
0
3      

Source

2015 UESTC Training for Data Structures

線段樹區間更新的模闆題,重寫了一下,發現太手生了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N = 100005;
int a[N],n,m;

struct node
{
    int l,r;
    ll sum,lazy;
}tree[N<<4];

void push_up(int rt)
{
    tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
}
void push_down(int rt,int m)
{
    if(tree[rt].lazy)
    {
        tree[rt<<1].lazy += tree[rt].lazy;
        tree[rt<<1|1].lazy += tree[rt].lazy;
        tree[rt<<1].sum += tree[rt].lazy * (m-(m>>1));
        tree[rt<<1|1].sum += tree[rt].lazy * (m>>1);
        tree[rt].lazy = 0;
    }
}
void build(int l,int r,int rt)
{
    tree[rt].l = l;
    tree[rt].r = r;
    tree[rt].sum = tree[rt].lazy = 0;
    if(l == r)
        tree[rt].sum = a[l];
    else
    {
        int mid = (l+r)>>1;
        build(l,mid,rt<<1);
        build(mid+1,r,rt<<1|1);
        push_up(rt);
    }
}

void update(int val,int l,int r,int rt)
{
    if(tree[rt].l == l && tree[rt].r == r)
    {
        tree[rt].lazy += 1ll*val;
        tree[rt].sum += 1ll*val*(r-l+1);
        return;
    }
    if(tree[rt].l == tree[rt].r)
        return;

    push_down(rt,tree[rt].r-tree[rt].l+1);
    int mid = (tree[rt].l+tree[rt].r)>>1;
    if(r <= mid)
        update(val,l,r,rt<<1);
    else if(l > mid)
        update(val,l,r,rt<<1|1);
    else
    {
        update(val,l,mid,rt<<1);
        update(val,mid+1,r,rt<<1|1);
    }
    push_up(rt);
}
ll query(int l,int r,int rt)
{
    if(tree[rt].l == l && tree[rt].r == r)
        return tree[rt].sum;
    push_down(rt,tree[rt].r-tree[rt].l+1);

    int mid = (tree[rt].l+tree[rt].r)>>1;
    ll ans = 0;
    if(r <= mid)
        ans += query(l,r,rt<<1);
    else if(l > mid)
        ans += query(l,r,rt<<1|1);
    else
    {
        ans += query(l,mid,rt<<1);
        ans += query(mid+1,r,rt<<1|1);
    }
    //printf("dsjilsdfgsd f\n");
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
        scanf("%d",&a[i]);
    build(1,n,1);
    scanf("%d",&m);
    while(m--)
    {
        int l,r,val;
        scanf("%d%d%d",&l,&r,&val);
        update(val,l,r,1);
        //printf("dsjils\n");
        printf("%lld\n",query(l,r,1));
    }
    return 0;
}
           

繼續閱讀