poj 3468 线段树lazy

题目：

A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072KTotal Submissions: 102981 Accepted: 32160Case Time Limit: 2000MS

Description

You have N integers, A₁, A₂, ... , A_N. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000. The second line contains N numbers, the initial values of A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000. Each of the next Q lines represents an operation. "C a b c" means adding c to each of A_a, A_a+1, ... , A_b. -10000 ≤ c ≤ 10000. "Q a b" means querying the sum of A_a, A_a+1, ... , A_b.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4

Sample Output

4 55 9 15

Hint

The sums may exceed the range of 32-bit integers.

代码：

pushdown的时候要向下累加。

#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<ctype.h> //tower() #include<set> #include<map> #include<iomanip>// cout<<setprecision(1)<<fixed<<a; #include<vector> #include<cmath> #include<algorithm> #include<bitset> #include<limits.h> #include<stack> #include<queue> using namespace std; const __int64 maxn=100010; const __int64 inf=0x7fffffff; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 __int64 add[maxn<<2];//维护当前lazy值 __int64 sum[maxn<<2];//线段树维护当前区间和 void pushup(__int64 rt){//当前结点信息更新到父结点 sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void pushdown(__int64 rt,__int64 num){ if(add[rt]){ add[rt<<1]+=add[rt]; //+= not = add[rt<<1|1]+=add[rt]; sum[rt<<1]+=add[rt]*(num-(num>>1)); sum[rt<<1|1]+=add[rt]*(num>>1); add[rt]=0; } } void build(__int64 l,__int64 r,__int64 rt){ add[rt]=0; if(l==r){ scanf("%I64d",&sum[rt]); return; } __int64 mid=(l+r)>>1; build(lson); build(rson); pushup(rt); } void update(__int64 a,__int64 b,__int64 c,__int64 l,__int64 r,__int64 rt){ if(a<=l&&b>=r){ add[rt]+=c; //+= not = sum[rt]+=c*(r-l+1); return; } pushdown(rt,r-l+1); __int64 mid=(l+r)>>1; if(a<=mid) update(a,b,c,lson); if(b>mid) update(a,b,c,rson); pushup(rt); } __int64 query(__int64 a,__int64 b,__int64 l,__int64 r,__int64 rt){ if(a<=l&&b>=r) return sum[rt]; pushdown(rt,r-l+1); __int64 mid=(l+r)>>1; __int64 s=0; if(a<=mid) s+=query(a,b,lson); if(b>mid) s+=query(a,b,rson); return s; } int main(){//G++:5888K 2985MS C++:5360K 2000MS __int64 n,m,a,b,c; char s[2]; while(scanf("%I64d%I64d",&n,&m)==2){ memset(sum,0,sizeof(sum)); build(1,n,1); while(m--){ scanf("%s",s); if(s[0]=='Q'){//查询 scanf("%I64d%I64d",&a,&b); printf("%I64d\n",query(a,b,1,n,1)); } else{//染色 scanf("%I64d%I64d%I64d",&a,&b,&c); update(a,b,c,1,n,1); } } } return 0; }