| Time Limit: 5000MS | Memory Limit: 131072K | |
| Total Submissions: 47174 | Accepted: 13844 | |
| 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
A[i]...A[n]的共同增量，n是数组的大小。那么update操作可以转化为：
1）令delta[s] = delta[s] + d，表示将A[s]...A[n]同时增加d，但这样A[t+1]...A[n]就多加了d，所以
2）再令delta[t+1] = delta[t+1] - d，表示将A[t+1]...A[n]同时减d
然后来看查询操作query(s, t)，求A[s]...A[t]的区间和，转化为求前缀和，设sum[i] = A[1]+...+A[i]，则
A[s]+...+A[t] = sum[t] - sum[s-1]，
那么前缀和sum[x]又如何求呢？它由两部分组成，一是数组的原始和，二是该区间内的累计增量和, 把数组A的原始
值保存在数组org中，并且delta[i]对sum[x]的贡献值为delta[i]*(x+1-i)，那么
sum[x] = org[1]+...+org[x] + delta[1]*x + delta[2]*(x-1) + delta[3]*(x-2)+...+delta[x]*1
= org[1]+...+org[x] + segma(delta[i]*(x+1-i))
= segma(org[i]) + (x+1)*segma(delta[i]) - segma(delta[i]*i)，1 <= i <= x
=segma(org[i]-delta[i]*i)+(x+1)*delta[i], i<=1<=x //by huicpc0207 修改 这里就可以转化为两个个数组
这其实就是三个数组org[i], delta[i]和delta[i]*i的前缀和，org[i]的前缀和保持不变，事先就可以求出来，delta[i]和
delta[i]*i的前缀和是不断变化的，可以用两个树状数组来维护。
1 #include <iostream> 2 #include <algorithm> 3 #include <stdio.h> 4 #include <string.h> 5 #include <math.h> 6 using namespace std; 7 #define ll long long int 8 ll a[510000];//维护delta[] 9 ll a1[510000];//维护delta[]*i 10 ll b[510000];//本来的数组和 11 int n; 12 int lowbit(int x) 13 { 14 return x&(-x); 15 } 16 void update(ll *arry,int x,int d) 17 { 18 while(x<=n) 19 { 20 arry[x]+=d; 21 x+=lowbit(x); 22 } 23 } 24 ll fun(ll *arry,int x) 25 { 26 ll sum=0; 27 while(x>0) 28 { 29 sum+=arry[x]; 30 x-=lowbit(x); 31 } 32 return sum; 33 } 34 int main() 35 { 36 //freopen("int.txt","r",stdin); 37 int k; 38 int x,i,y,z; 39 scanf("%d%d",&n,&k); 40 memset(b,0,sizeof(b)); 41 memset(a,0,sizeof(a)); 42 memset(a1,0,sizeof(a1)); 43 for(i=1;i<=n;i++) 44 { 45 scanf("%d",&x); 46 b[i]+=b[i-1]+x; 47 } 48 char c; 49 for(i=0;i<k;i++) 50 { 51 c=getchar(); 52 c=getchar(); 53 if(c=='C') 54 { 55 scanf("%d%d%d",&x,&y,&z); 56 update(a,x,z); 57 update(a,y+1,-z); 58 update(a1,x,z*x); 59 update(a1,y+1,-z*(y+1)); 60 } 61 else 62 { 63 scanf("%d%d",&x,&y); 64 ll sum=-b[x-1]-x*fun(a,x-1)+fun(a1,x-1); 65 sum+=b[y]+(y+1)*fun(a,y)-fun(a1,y); 66 printf("%I64d ",sum); 67 } 68 } 69 }