Time Limit: 5000MS | Memory Limit: 131072K | |
Total Submissions: 67497 | Accepted: 20813 | |
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
有n个整数, v1,v2,v3...vn,可以进行两种操作,第一种是Q(x,y),输出区间x~y的和,第二种是C(x,y,z),区间x~y内所有数+z,不多说了,直接上线段树。。。
#include <iostream> #include <stdlib.h> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 100010; struct node { __int64 sum,mark; //区间和,懒惰标记 }q[N*4]; int v[N]; //输入的序列 void build(int l,int r,int rt) //建树 { q[rt].sum=0; q[rt].mark=0; if(l==r) { q[rt].sum+=v[r]; return ; } int mid=(l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); q[rt].sum=q[rt<<1].sum + q[rt<<1|1].sum; //累计左右区间的和 } void update(int l,int r,int rt) //节点rt没标记,则推出,否则计算出左右区间的和,将标记传下去 { if(q[rt].mark) { int mid=(l+r)>>1; q[rt<<1].sum += q[rt].mark*(__int64)(mid-l+1); q[rt<<1|1].sum += q[rt].mark*(__int64)(r-mid); q[rt<<1].mark += q[rt].mark; q[rt<<1|1].mark += q[rt].mark; q[rt].mark=0; } } __int64 Query(int x,int y,int l,int r,int rt) { if(x>r || y<l) return 0; if(x<=l && y>=r) return q[rt].sum; update(l,r,rt); int mid=(l+r)>>1; return Query(x,y,l,mid,rt<<1) + Query(x,y,mid+1,r,rt<<1|1); } void add(int x,int y,int z,int l,int r,int rt) { if(x>r || y<l) return ; if(x<=l && y>=r) { q[rt].sum+=(__int64)(r-l+1)*z; q[rt].mark+=z; return ; } update(l,r,rt); int mid=(l+r)>>1; if(x<=mid) add(x,y,z,l,mid,rt<<1); if(y>mid) add(x,y,z,mid+1,r,rt<<1|1); q[rt].sum=q[rt<<1].sum + q[rt<<1|1].sum; } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) scanf("%d",&v[i]); getchar(); build(1,n,1); for(int i=0;i<m;i++) { char s; scanf("%c",&s); if(s=='Q') { int x,y; scanf("%d%d",&x,&y); __int64 ans=Query(x,y,1,n,1); printf("%I64d\n",ans); } else if(s=='C') { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z,1,n,1); } getchar(); } } return 0; }