秋实大哥与花

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

线段树裸题

代码：

#include <bits/stdc++.h> using namespace std; const int maxn=1e5+6; int n,a[maxn],q; struct node { int l,r; long long sum,lazy; void update(long long x) { sum+=(long long)((r-l+1)*x); lazy+=x; } }tree[maxn*4]; void push_up(int x) { tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum; } void push_down(int x) { int lazyval=tree[x].lazy; if(lazyval){ tree[x<<1].update(lazyval); tree[x<<1|1].update(lazyval); tree[x].lazy=0; } } void build(int x,int l,int r) { tree[x].l=l,tree[x].r=r; tree[x].sum=tree[x].lazy=0; if(l==r){ tree[x].sum=a[l]; }else{ int mid=(l+r)/2; build(x<<1,l,mid); build(x<<1|1,mid+1,r); push_up(x); } } void update(int x,int l,int r,long long val) { int L=tree[x].l,R=tree[x].r; if(l<=L&&R<=r) tree[x].update(val); else{ push_down(x); int mid=(L+R)/2; if(mid>=l)update(x<<1,l,r,val); if(r>mid)update(x<<1|1,l,r,val); push_up(x); } } long long query(int x,int l,int r) { int L=tree[x].l,R=tree[x].r; if(l<=L&&R<=r) return tree[x].sum; else{ push_down(x); long long ans=0; int mid=(L+R)/2; if(mid>=l)ans+=query(x<<1,l,r); if(r>mid)ans+=query(x<<1|1,l,r); push_up(x); return ans; } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); scanf("%d",&q); for(int i=1;i<=q;i++){ int l,r,val; scanf("%d%d%d",&l,&r,&val); update(1,l,r,val); printf("%lld\n",query(1,l,r)); } }