首页 > 代码库 > POJ 3468

POJ 3468

2024-07-18 00:18:17   218人阅读

A Simple Problem with Integers

Time Limit:5000MS   Memory Limit:131072K
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 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 4

Sample Output

455915

Hint

The sums may exceed the range of 32-bit integers.
 
题解：本题也是线段树系列的模板题之一，要求的是成段更新+懒惰标记。PS：原题的说明有问题，上面说的“C a b c”中的c的范围其实在int32之外，需要使用long long，否则定是WA，真心坑爹，连WA多次，还是在discuss中看到的原因。
 
稍微讲解下代码中的一些细节: step<<1 与 step<<1|1，意思分别是step*2 和step*+1，具体为什么，可以回去复习一下位运算
 
转自 http://www.cnblogs.com/kevince/p/3888608.html

 

  1 #include<iostream>  2 #include<cstring>  3 #include<cstdlib>  4 #include<cstdio>  5 #include<algorithm>  6 #include<cmath>  7 #include<queue>  8 #include<map>  9  10 #define N 100010 11 #define M 15 12 #define mod 1000000007 13 #define mod2 100000000 14 #define ll long long 15 #define maxi(a,b) (a)>(b)? (a) : (b) 16 #define mini(a,b) (a)<(b)? (a) : (b) 17  18 using namespace std; 19  20 int n,q; 21 int x[N]; 22 char ch; 23 int a,b,c; 24  25 struct node 26 { 27     ll mark,sum; 28 }tree[4*N]; 29  30 void update(int l,int r,int i) 31 { 32     if(!tree[i].mark) return; 33     int mid=(l+r)/2; 34     tree[2*i].sum+=tree[i].mark*(ll)(mid-l+1); 35     tree[2*i+1].sum+=tree[i].mark*(ll)(r-mid); 36     tree[2*i].mark+=tree[i].mark; 37     tree[2*i+1].mark+=tree[i].mark; 38     tree[i].mark=0; 39  40 } 41  42 ll query(int tl,int tr,int l,int r,int i) 43 { 44     if(tl>r || tr<l) 45         return 0; 46     if(tl<=l && r<=tr) 47         return tree[i].sum; 48     update(l,r,i); 49     int mid=(l+r)/2; 50  51     return query(tl,tr,l,mid,2*i)+query(tl,tr,mid+1,r,2*i+1); 52 } 53  54 void addd(int tl,int tr,int l,int r,int i,int val) 55 { 56     if(tl>r || tr<l) 57         return; 58     if(tl<=l && tr>=r){ 59         tree[i].sum+=val*(ll)(r-l+1); 60         tree[i].mark+=val; 61         return; 62     } 63     update(l,r,i); 64     int mid=(l+r)/2; 65     addd(tl,tr,l,mid,2*i,val); 66     addd(tl,tr,mid+1,r,2*i+1,val); 67     tree[i].sum=tree[2*i].sum+tree[2*i+1].sum; 68 } 69  70 void build_tree(int l,int r,int i) 71 { 72     if(l==r){ 73         tree[i].sum=x[l]; 74         return; 75     } 76     int mid=(l+r)/2; 77     build_tree(l,mid,2*i); 78     build_tree(mid+1,r,2*i+1); 79     tree[i].sum=tree[2*i].sum+tree[2*i+1].sum; 80 } 81  82 int main() 83 { 84     int i; 85    // freopen("data.in","r",stdin); 86     //scanf("%d",&T); 87     //for(int cnt=1;cnt<=T;cnt++) 88     //while(T--) 89     while(scanf("%d%d",&n,&q)!=EOF) 90     { 91        // printf(" %d %d \n",n,q); 92        for(i=1;i<=n;i++) scanf("%d",&x[i]); 93       // printf(" 1\n"); 94        memset(tree,0,sizeof(tree)); 95        build_tree(1,n,1); 96  97  98       //  printf(" 2\n"); 99        getchar();100        while(q--){101           //  printf(" 3\n");102             scanf("%c",&ch);103           //  printf(" %c\n",ch);104             if(ch==‘C‘){105                 //printf(" 31\n");106                 scanf("%d%d%d",&a,&b,&c);107                 getchar();108                 addd(a,b,1,n,1,c);109 110             }111             else{112                   //  printf(" 32\n");113                 scanf("%d%d",&a,&b);114                 getchar();115                 ll ans=query(a,b,1,n,1);116                 printf("%I64d\n",ans);117             }118        }119     }120 121     return 0;122 }

 


联系
我们