Description
You have N integers, A1, A2, ... , AN. 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 A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
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.
题意：裸线段树 区间更新/查询
题解：线段树每次写都有不同程度的错误.too vegatable
1.延迟标记的add 都要初始化为0
2.延迟的传递是累加而不是赋值
具体看代码。
/******************************
code by drizzle
blog: www.cnblogs.com/hsd-/
^ ^ ^ ^
O O
******************************/
//#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>
#include<cmath>
#define ll long long
#define PI acos(-1.0)
#define mod 1000000007
using namespace std;
struct node
{
ll l,r;
ll add;
ll sum;
} tree[];
void buildtree(ll root,ll left,ll right)
{
tree[root].l=left;
tree[root].r=right;
tree[root].add=;//wa点 所有的延迟标记都要初始化
if(left==right)//不能放到下面的if中
{ ll exm;
scanf("%lld",&exm);
tree[root].sum=exm;
return ;
}
ll mid=(left+right)>>;
buildtree(root<<,left,mid);
buildtree(root<<|,mid+,right);
tree[root].sum=tree[root<<].sum+tree[root<<|].sum;
}
void pushdown(ll root)
{
if(tree[root].add==) return ;
tree[root<<].add+=tree[root].add;//wa点 这里是增加而不是赋值
tree[root<<|].add+=tree[root].add;
tree[root<<].sum+=(tree[root<<].r-tree[root<<].l+)*tree[root].add;
tree[root<<|].sum+=(tree[root<<|].r-tree[root<<|].l+)*tree[root].add;
tree[root].add=;
}
void updata(ll root,ll left,ll right,ll c)
{
if(tree[root].l==left&&tree[root].r==right)
{
tree[root].add+=c;//wa点 这里是增加而不是赋值
tree[root].sum+=(right-left+)*c;
return ;
}
pushdown(root);
ll mid=(tree[root].l+tree[root].r)>>;
if(right<=mid)
updata(root<<,left,right,c);
else
{
if(left>mid)
updata(root<<|,left,right,c);
else
{
updata(root<<,left,mid,c);
updata(root<<|,mid+,right,c);
}
}
tree[root].sum=tree[root<<].sum+tree[root<<|].sum;
}
ll query(ll root,ll left,ll right)
{
if(tree[root].l==left&&tree[root].r==right)
{
return tree[root].sum;
}
pushdown(root);
ll mid=(tree[root].l+tree[root].r)>>;
if(right<=mid)
return query(root<<,left,right);
else
{
if(left>mid)
return query(root<<|,left,right);
else
return query(root<<,left,mid)+query(root<<|,mid+,right);
}
}
ll n,q;
char what;
ll l1,r1,ad;
int main()
{
while(~scanf("%lld %lld",&n,&q))
{
buildtree(,,n);
getchar();
for(ll i=; i<=q; i++)
{
scanf("%c %lld %lld",&what,&l1,&r1);
if(what=='Q')
printf("%lld\n",query(,l1,r1));
else
{
scanf("%lld",&ad);
updata(,l1,r1,ad);
}
getchar();
}
}
return ;
}
/*
10 10
1 2 3 4 5 6 7 8 9 10
C 1 10 1
Q 2 3 10 10
1 2 3 4 5 6 7 8 9 10
C 1 5 1
Q 4 6
*/