A Simple Problem with Integers
| Time Limit: 5000MS | Memory Limit: 131072K | |
| Total Submissions: 67511 | Accepted: 20818 | |
| Case Time Limit: 2000MS |
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>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
using namespace std;
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define lr rt<<1
#define rr rt<<1|1
typedef long long LL;
const int oo = 1e9+;
const double PI = acos(-1.0);
const double eps = 1e- ;
const int N = ;
const int mod = ;
int n , m ;
LL sum[N<<] , lazy[N<<] , e[N] , tot ; void Up( int rt ) {
sum[rt] = sum[lr] + sum[rr];
}
void Down( int l , int r , int rt ) {
if( lazy[rt] != ) {
int mid = (l+r)>>;
sum[lr] += lazy[rt]*(mid-l+) , sum[rr] += lazy[rt]*(r-mid);
lazy[lr] += lazy[rt] , lazy[rr] += lazy[rt];
lazy[rt] = ;
}
}
void build( int l , int r , int rt ){
lazy[rt] = ;
if( l == r ) {
sum[rt] = e[tot++];
return ;
}
int mid = (l+r)>>;
build(lson),build(rson);
Up(rt);
}
void update( int l , int r , int rt , int L , int R , LL val ) {
if( L == l && r == R ) {
sum[rt] += val*(r-l+) ;
lazy[rt] += val;
return ;
}
Down( l , r , rt );
int mid = (l+r)>>;
if( R <= mid ) update(lson,L,R,val);
else if( L > mid ) update(rson,L,R,val);
else update(lson,L,mid,val) , update(rson,mid+,R,val);
Up(rt);
}
LL query( int l , int r , int rt , int L , int R ) {
if( L == l && r == R ) {
return sum[rt];
}
Down(l,r,rt);
int mid = (l+r)>>;
if( R <= mid ) return query(lson,L,R);
else if( L > mid ) return query(rson,L,R);
else return query(lson,L,mid) + query(rson,mid+,R);
} int main()
{
#ifdef LOCAL
freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif // LOCAL
char s[]; int x , y ; LL c ;
while( ~scanf("%d%d",&n,&m ) ) {
tot = ;
for( int i = ; i < n ; ++i ) {
scanf("%I64d",&e[i]);
}
build(root);
while(m--) {
scanf("%s",s);
if( s[] == 'Q' ) {
scanf("%d%d",&x,&y);
printf("%I64d\n",query(root,x,y));
}
else {
scanf("%d%d%I64d",&x,&y,&c);
update(root,x,y,c);
}
}
}
}