| Time Limit: 5000MS | Memory Limit: 131072K | |
| Total Submissions: 79137 | Accepted: 24395 | |
| 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
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAX 100000+10
using namespace std;
long long add[MAX<<2];
long long sum[MAX<<2];
void pushup(int o)
{
sum[o]=sum[o<<1]+sum[o<<1|1];
}
void pushdown(int o,int m)
{
if(add[o])
{
add[o<<1]+=add[o];
add[o<<1|1]+=add[o];
sum[o<<1]+=add[o]*(m-(m>>1));
sum[o<<1|1]+=add[o]*(m>>1);
add[o]=0;
}
}
void gettree(int o,int l,int r)
{
add[o]=0;
if(l==r)
{
scanf("%lld",&sum[o]);
return ;
}
int mid=(l+r)>>1;
gettree(o<<1,l,mid);
gettree(o<<1|1,mid+1,r);
pushup(o);
}
void update(int o,int l,int r,int L,int R,int val)
{
if(L<=l&&R>=r)
{
add[o]+=val;
sum[o]+=val*(r-l+1);
return ;
}
pushdown(o,r-l+1);
int mid=(l+r)>>1;
if(L<=mid)
update(o<<1,l,mid,L,R,val);
if(R>mid)
update(o<<1|1,mid+1,r,L,R,val);
pushup(o);
}
long long find(int o,int l,int r,int L,int R)
{
if(L<=l&&R>=r)
{
return sum[o];
}
pushdown(o,r-l+1);
long long ans=0;
int mid=(l+r)>>1;
if(L<=mid)
ans+=find(o<<1,l,mid,L,R);
if(R>mid)
ans+=find(o<<1|1,mid+1,r,L,R);
return ans;
}
int main()
{
int n,m,i,j;
int a,b,c;
char d[12];
while(scanf("%d%d",&n,&m)!=EOF)
{
gettree(1,1,n);
for(i=1;i<=m;i++)
{
scanf("%s%d%d",d,&a,&b);
if(d[0]==‘Q‘)
printf("%lld\n",find(1,1,n,a,b));
else
{
scanf("%d",&c);
update(1,1,n,a,b,c);
}
}
}
return 0;
}
poj 3468 A Simple Problem with Integers【线段树区间修改】
原文：http://www.cnblogs.com/tonghao/p/4792865.html