A Simple Problem with Integers
| Time Limit: 5000MS | Memory Limit: 131072K | |
| Total Submissions: 56971 | Accepted: 17284 | |
| 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
POJ Monthly--2007.11.25, Yang Yi
传送门：POJ 3468 A Simple Problem with Integers
传送门：POJ 3468 A Simple Problem with Integers
题目分析：赤果果的区间修改区间查询，线段树搞之。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long BigInt ;
#define ll o << 1
#define rr o << 1 | 1
#define lson l , m , ll
#define rson m + 1 , r , rr
const int maxN = 1000005 ;
struct Seg_Tree {
BigInt sum , add ;
int l , r ;
int len () {
return r - l + 1 ;
}
int mid () {
return ( l + r ) >> 1 ;
}
} tree[maxN] ;
void PushUp ( int o ) {
tree[o].sum = tree[ll].sum + tree[rr].sum ;
}
void PushDown ( int o ) {
if ( tree[o].add ) {
int len = tree[o].len () ;
tree[ll].add += tree[o].add ;
tree[rr].add += tree[o].add ;
tree[ll].sum += tree[o].add * ( len - ( len >> 1 ) ) ;
tree[rr].sum += tree[o].add * ( len >> 1 ) ;
tree[o].add = 0 ;
}
}
void Build ( int l , int r , int o ) {
tree[o].l = l ;
tree[o].r = r ;
tree[o].add = 0 ;
if ( tree[o].l == tree[o].r ) {
scanf ( "%lld" , &tree[o].sum ) ;
return ;
}
int m = tree[o].mid () ;
Build ( lson ) ;
Build ( rson ) ;
PushUp ( o ) ;
}
void Update ( int L , int R , int o , int v ) {
if ( L <= tree[o].l && tree[o].r <= R ) {
tree[o].add += v ;
tree[o].sum += v * tree[o].len () ;
return ;
}
PushDown ( o ) ;
int m = tree[o].mid () ;
if ( L <= m ) Update ( L , R , ll , v ) ;
if ( m < R ) Update ( L , R , rr , v ) ;
PushUp ( o ) ;
}
BigInt anssum ;
void Query ( int L , int R , int o ) {
if ( L <= tree[o].l && tree[o].r <= R ) {
anssum += tree[o].sum ;
return ;
}
PushDown ( o ) ;
int m = tree[o].mid () ;
if ( L <= m ) Query ( L , R , ll ) ;
if ( m < R ) Query ( L , R , rr ) ;
}
void work () {
int n , m , L , R , v ;
char ch[5] ;
while ( ~scanf ( "%d%d" , &n , &m ) ) {
Build ( 1 , n , 1 ) ;
while ( m -- ) {
scanf ( "%s" , ch ) ;
if ( ch[0] == 'Q' ) {
anssum = 0 ;
scanf ( "%d%d" , &L , &R ) ;
Query ( L , R , 1 ) ;
printf ( "%lld\n" , anssum ) ;
}
if ( ch[0] == 'C' ) {
scanf ( "%d%d%d" , &L , &R , &v ) ;
Update ( L , R , 1 , v ) ;
}
}
}
}
int main () {
work () ;
return 0 ;
}