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.
Source
POJ Monthly--2007.11.25, Yang Yi
题意很明显，只有两种操作，需要使用线段树（对于区间的修改~）：update（)和query（） 用到了__int64需要注意
代码如下：
题意很明显，只有两种操作，需要使用线段树（对于区间的修改~）：update（)和query（） 用到了__int64需要注意
代码如下：
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
const int MAXN = 100000 + 10;
struct Node{
int l, r;
__int64 k, add;
};
Node znode[4*MAXN];
__int64 zfun(__int64 a, __int64 b) {
return a+b;
}
void build(int l, int r, int n){
int mid = (l+r)/2;
znode[n].l = l;
znode[n].r = r;
znode[n].add = 0;
znode[n].k = 0;
if(l==r) return;
else {
build(l, mid, 2*n);
build(mid+1, r, 2*n+1);
}
}
void update(int l, int r, int n, __int64 val){
znode[n].k += (r-l+1)*val;
if(l<=znode[n].l && znode[n].r<=r) znode[n].add += val;
else{
int mid = (znode[n].l + znode[n].r) / 2;
if(r<=mid) update(l, r, 2*n, val);
else if(l>mid) update(l, r, 2*n+1, val);
else {
update(l, mid, 2*n, val);
update(mid+1, r, 2*n+1, val);
}
}
}
__int64 query(int l, int r, int n){ //l、r是待查询的区间端点
int mid = (znode[n].l + znode[n].r) / 2;
if(znode[n].l==l && znode[n].r==r) return znode[n].k;
else{
if(znode[n].add){ //下放延迟的标记
znode[2*n].add += znode[n].add;
znode[2*n].k += znode[n].add*(znode[2*n].r-znode[2*n].l+1);
znode[2*n+1].add += znode[n].add;
znode[2*n+1].k += znode[n].add*(znode[2*n+1].r-znode[2*n+1].l+1);
znode[n].add = 0;
}
if(r<=mid) return query(l, r, 2*n);
else if(l>mid) return query(l, r, 2*n+1);
else return zfun(query(l, mid, 2*n), query(mid+1, r, 2*n+1));
}
}
int main(){
// freopen("in.txt", "r", stdin);
int id = 1, n, m;
while(scanf("%d%d", &n, &m)!=EOF){
build(1, n, 1);
int i, s;
for(i=1; i<=n; i++){
scanf("%d", &s);
update(i, i, 1, s);
}
char ch[2];
int a, b;
__int64 c;
for(i=1; i<=m; i++){
scanf("%s%d%d", ch, &a, &b);
if(ch[0]=='Q') {
__int64 ans = query(a, b, 1);
printf("%I64d\n", ans);
}
else if(ch[0]=='C'){
scanf("%I64d", &c);
update(a, b, 1, c);
}
}
}
return 0;
}
