A Simple Problem with Integers
| Time Limit: 5000MS | Memory Limit: 131072K | |
| Total Submissions: 53749 | Accepted: 16131 | |
| 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
//更新某一段区域的时候，采用延迟标记~~
代码：
#include "cstdio" //poj 3468 lazy操作
#include "cstring"
#include "iostream"
using namespace std; #define N 100005
#define LL long long struct node{
int x,y;
LL sum;
LL add; //记录以当前节点为根节点的树中需要增加的值
}a[*N]; void Build(int t,int x,int y)
{
a[t].x = x;
a[t].y = y;
a[t].sum = a[t].add = ;
if(a[t].x == a[t].y) //到了叶子节点
{
scanf("%lld",&a[t].sum);
return ;
}
int mid = (a[t].x + a[t].y)/;
Build(t<<,x,mid);
Build(t<<|,mid+,y);
a[t].sum = a[t<<].sum + a[t<<|].sum;
} void Push_down(int t) //将add(增值)向下推一级
{
LL add = a[t].add;
a[t<<].add += add;
a[t<<|].add += add;
a[t<<].sum += add*(a[t<<].y-a[t<<].x+);
a[t<<|].sum += add*(a[t<<|].y-a[t<<|].x+);
a[t].add = ;
} LL Query(int t,int x,int y)
{
if(a[t].x==x &&a[t].y==y)
return a[t].sum;
Push_down(t);
int mid = (a[t].x + a[t].y)/;
if(y<=mid)
return Query(t<<,x,y);
if(x>mid)
return Query(t<<|,x,y);
else
return Query(t<<,x,mid) + Query(t<<|,mid+,y);
} void Add(int t,int x,int y,int k)
{
if(a[t].x==x && a[t].y==y) //不在推到叶子节点，t下的子孙要增加的值存入a[t].add中
{
a[t].add += k;
a[t].sum += (a[t].y-a[t].x+)*k;
return ;
}
a[t].sum += (y-x+)*k;
Push_down(t);
int mid = (a[t].x+a[t].y)/;
if(y<=mid)
Add(t<<,x,y,k);
else if(x>mid)
Add(t<<|,x,y,k);
else
{
Add(t<<,x,mid,k);
Add(t<<|,mid+,y,k);
}
} int main()
{
int n,m;
char ch;
int x,y,k;
scanf("%d %d",&n,&m);
Build(,,n);
while(m--)
{
getchar();
scanf("%c %d %d",&ch,&x,&y);
if(ch=='Q')
printf("%lld\n",Query(,x,y));
else
{
scanf("%d",&k);
Add(,x,y,k);
}
}
return ;
}