Description
You have N integers, A, A, ... , A. 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. -1000000000 ≤ A ≤ 1000000000. Each of the next Q lines represents an operation. "C a b c" means adding c to each of A, A, ... , A. -10000 ≤ c ≤ 10000. "Q a b" means querying the sum of A, A, ... , A.
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.
这是对区间所有点增固定值类的线段树。
代码：
#include <iostream>
#include <cstdio>
#define LL long long using namespace std; int n, q; //线段树
const int maxn = 100000;
struct node
{
int lt, rt;
LL val, add;
}tree[4*maxn]; //建立线段树
void Build(int lt, int rt, int id)
{
tree[id].lt = lt;
tree[id].rt = rt;
tree[id].val = 0;//每段的初值，根据题目要求
tree[id].add = 0;
if (lt == rt)
{
scanf("%I64d", &tree[id].val);
//tree[id].add = ??;
return;
}
int mid = (lt + rt) >> 1;
Build(lt, mid, id << 1);
Build(mid + 1, rt, id << 1 | 1);
tree[id].val = tree[id<<1].val + tree[id<<1|1].val;
} void PushDown(int id, int pls)
{
tree[id<<1].add += tree[id].add;
//tree[id<<1].val += (pls-(pls>>1))*tree[id].add;
tree[id<<1].val += (tree[id<<1].rt-tree[id<<1].lt+1)*tree[id].add;
tree[id<<1|1].add += tree[id].add;
//tree[id<<1|1].val += (pls>>1)*tree[id].add;
tree[id<<1|1].val += (tree[id<<1|1].rt-tree[id<<1|1].lt+1)*tree[id].add;
tree[id].add = 0;
} //增加区间内每个点固定的值
void Add(int lt, int rt, int id, int pls)
{
if (lt <= tree[id].lt && rt >= tree[id].rt)
{
tree[id].add += pls;
tree[id].val += pls * (tree[id].rt-tree[id].lt+1);
return;
}
if (tree[id].add != 0)
{
PushDown(id, tree[id].rt-tree[id].lt+1);
}
int mid = (tree[id].lt + tree[id].rt) >> 1;
if (lt <= mid)
Add(lt, rt, id<<1, pls);
if (rt > mid)
Add(lt, rt, id<<1|1, pls);
tree[id].val = tree[id<<1].val + tree[id<<1|1].val;
} LL Query(int lt, int rt, int id)
{
if (lt <= tree[id].lt && rt >= tree[id].rt)
return tree[id].val;
if (tree[id].add != 0)
{
PushDown(id, tree[id].rt-tree[id].lt+1);
}
int mid = (tree[id].lt + tree[id].rt) >> 1;
LL ans = 0;
if (lt <= mid)
ans += Query(lt, rt, id<<1);
if (rt > mid)
ans += Query(lt, rt, id<<1|1);
return ans; } int main()
{
//freopen("in.txt", "r", stdin);
char op;
int a, b, k;
while (scanf("%d%d", &n, &q) != EOF)
{
Build(1, n, 1);
for (int i = 0; i < q; ++i)
{
getchar();
op = getchar();
getchar();
scanf("%d%d", &a, &b);
if (op == 'Q')
printf("%I64d\n", Query(a, b, 1));
else
{
scanf("%d", &k);
Add(a, b, 1, k);
}
}
}
return 0;
}