Time Limit:5000MS Memory Limit:131072KB 64bit IO Format:%I64d & %I64u
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 abc" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000."Q ab" 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.
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 int a[100005],sum[450005],lazy[450005],ql,qr,c; 8 9 void down(int o,int l,int r) 10 { 11 if(lazy[o]!=0) 12 { 13 int mid=(l+r)/2; 14 lazy[o*2]=lazy[o*2]+lazy[o]; 15 lazy[o*2+1]=lazy[o*2+1]+lazy[o]; 16 sum[o*2]=sum[o*2]+lazy[o]*(mid-l+1); 17 sum[o*2+1]=sum[o*2+1]+lazy[o]*(r-mid); 18 lazy[o]=0; 19 } 20 } 21 22 void up(int o) 23 { 24 sum[o]=sum[o*2]+sum[o*2+1]; 25 } 26 27 void build(int o,int l,int r) 28 { 29 if(l==r) 30 { 31 sum[o]=a[l]; 32 return; 33 } 34 int mid=(l+r)/2; 35 build(o*2,l,mid); 36 build(o*2+1,mid+1,r); 37 up(o); 38 } 39 40 void update(int o,int l,int r) 41 { 42 if(ql<=l && qr>=r) 43 { 44 lazy[o]=lazy[o]+c; 45 sum[o]=sum[o]+c*(r-l+1); 46 return; 47 } 48 down(o,l,r); 49 int mid=(l+r)/2; 50 if(ql<=mid) 51 update(o*2,l,mid); 52 if(qr>mid) 53 update(o*2+1,mid+1,r); 54 up(o); 55 } 56 57 int query(int o,int l,int r) 58 { 59 if(ql<=l && qr>=r) 60 { 61 return sum[o]; 62 } 63 down(o,l,r); 64 int mid=(l+r)/2,ans=0; 65 if(ql<=mid) 66 ans=ans+query(o*2,l,mid); 67 if(qr>mid) 68 ans=ans+query(o*2+1,mid+1,r); 69 up(o); 70 return ans; 71 } 72 73 int main() 74 { 75 int n,q,i; 76 char sre[10]; 77 while(scanf("%d %d",&n,&q)!=EOF) 78 { 79 memset(sum,0,sizeof(sum)); 80 memset(lazy,0,sizeof(lazy)); 81 for(i=1;i<=n;i++) 82 scanf("%d",&a[i]); 83 84 build(1,1,n); 85 for(i=1;i<=q;i++) 86 { 87 scanf("%s %d %d",sre,&ql,&qr); 88 if(sre[0]=='C') 89 { 90 scanf("%d",&c); 91 update(1,1,n); 92 } 93 else 94 { 95 printf("%d\n",query(1,1,n)); 96 } 97 } 98 } 99 return 0;100 }
64位
1 #include2 #include 3 #include 4 using namespace std; 5 6 long long a[100005],sum[450005],lazy[450005],c; 7 int ql,qr; 8 9 void down(int o,int l,int r) 10 { 11 if(lazy[o]!=0) 12 { 13 int mid=(l+r)/2; 14 lazy[o*2]=lazy[o*2]+lazy[o]; 15 lazy[o*2+1]=lazy[o*2+1]+lazy[o]; 16 sum[o*2]=sum[o*2]+lazy[o]*(mid-l+1); 17 sum[o*2+1]=sum[o*2+1]+lazy[o]*(r-mid); 18 lazy[o]=0; 19 } 20 } 21 22 void up(int o) 23 { 24 sum[o]=sum[o*2]+sum[o*2+1]; 25 } 26 27 void build(int o,int l,int r) 28 { 29 if(l==r) 30 { 31 sum[o]=a[l]; 32 return; 33 } 34 int mid=(l+r)/2; 35 build(o*2,l,mid); 36 build(o*2+1,mid+1,r); 37 up(o); 38 } 39 40 void update(int o,int l,int r) 41 { 42 if(ql<=l && qr>=r) 43 { 44 lazy[o]=lazy[o]+c; 45 sum[o]=sum[o]+c*(r-l+1); 46 return; 47 } 48 down(o,l,r); 49 int mid=(l+r)/2; 50 if(ql<=mid) 51 update(o*2,l,mid); 52 if(qr>mid) 53 update(o*2+1,mid+1,r); 54 up(o); 55 } 56 57 long long query(int o,int l,int r) 58 { 59 if(ql<=l && qr>=r) 60 { 61 return sum[o]; 62 } 63 down(o,l,r); 64 int mid=(l+r)/2; 65 long long ans=0; 66 if(ql<=mid) 67 ans=ans+query(o*2,l,mid); 68 if(qr>mid) 69 ans=ans+query(o*2+1,mid+1,r); 70 up(o); 71 return ans; 72 } 73 74 int main() 75 { 76 int n,q,i; 77 char sre[10]; 78 while(scanf("%d %d",&n,&q)!=EOF) 79 { 80 memset(sum,0,sizeof(sum)); 81 memset(lazy,0,sizeof(lazy)); 82 for(i=1;i<=n;i++) 83 scanf("%lld",&a[i]); 84 build(1,1,n); 85 for(i=1;i<=q;i++) 86 { 87 scanf("%s %d %d",sre,&ql,&qr); 88 if(sre[0]=='C') 89 { 90 scanf("%lld",&c); 91 update(1,1,n); 92 } 93 else 94 { 95 printf("%lld\n",query(1,1,n)); 96 } 97 } 98 } 99 return 0;100 }