A Simple Problem with Integers
| Time Limit: 5000MS | Memory Limit: 131072K | |
| Total Submissions: 58269 | Accepted: 17753 | |
| Case Time Limit: 2000MS | ||
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
线段树，区间修改求和。
题意：
思路：
代码：
#include <iostream>
#include <stdio.h>
using namespace std; #define MAXN 100010 struct Node{
long long L,R;
long long sum; //当前区间的所有数的和
long long inc; //累加量
}a[MAXN*]; void Build(long long d,long long l,long long r) //建立线段树
{ //初始化当前节点的信息
a[d].L = l;
a[d].R = r;
a[d].inc = ; if(l==r){ //找到叶子节点
scanf("%I64d",&a[d].sum);
return ;
} //建立线段树
long long mid = (l+r)>>;
Build(d<<,l,mid);
Build(d<<|,mid+,r); //更新当前节点的信息
a[d].sum = a[d<<].sum + a[d<<|].sum;
} void Updata(long long d,long long l,long long r,long long v) //更新区间[l,r]的累加量为v
{
if(a[d].L==l && a[d].R==r){ //找到终止节点
a[d].inc += v;
return ;
} long long mid = (a[d].L+a[d].R)/;
a[d].sum += a[d].inc*(a[d].R - a[d].L + ); if(mid>=r){ //左孩子找
Updata(d<<,l,r,v);
}
else if(mid<l){ //右孩子找
Updata(d<<|,l,r,v);
}
else{ //左孩子、右孩子都找
Updata(d<<,l,mid,v);
Updata(d<<|,mid+,r,v);
} a[d].sum = a[d<<].sum + a[d<<|].sum
+ a[d<<].inc*(a[d<<].R - a[d<<].L + )
+ a[d<<|].inc*(a[d<<|].R - a[d<<|].L + );
} long long Query(long long d,long long l,long long r) //查询区间[l,r]的所有数的和
{
if(a[d].L==l && a[d].R==r){ //找到终止节点
return a[d].sum + a[d].inc * (r-l+);
} long long mid = (a[d].L+a[d].R)/;
//更新每个节点的sum
a[d].sum += a[d].inc * (a[d].R - a[d].L + );
a[d<<].inc += a[d].inc;
a[d<<|].inc += a[d].inc;
a[d].inc = ; //Updata(d<<1,a[d<<1].L,a[d<<1].R,a[d].inc);
//Updata(d<<1|1,a[d<<1|1].L,a[d<<1|1].R,a[d].inc); if(mid>=r){ //左孩子找
return Query(d<<,l,r);
}
else if(mid<l){ //右孩子找
return Query(d<<|,l,r);
}
else{ //左孩子、右孩子都找
return Query(d<<,l,mid) + Query(d<<|,mid+,r);
}
a[d].sum = a[d<<].sum + a[d<<|].sum
+ a[d<<].inc*(a[d<<].R - a[d<<].L + )
+ a[d<<|].inc*(a[d<<|].R - a[d<<|].L + );
} int main()
{
long long n,q,A,B;
long long v;
scanf("%I64d%I64d",&n,&q);
Build(,,n);
while(q--){ //q次询问
char c[];
scanf("%s",&c);
switch(c[]){
case 'Q':
scanf("%I64d%I64d",&A,&B);
printf("%I64d\n",Query(,A,B)); //输出区间[A,B]所有数的和
break;
case 'C':
scanf("%I64d%I64d%I64d",&A,&B,&v);
Updata(,A,B,v);
break;
default:break;
}
}
return ;
}
Freecode : www.cnblogs.com/yym2013