POJ3468

A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072KTotal Submissions: 105107 Accepted: 32795Case Time Limit: 2000MS

Description

You have N integers, A₁, A₂, ... , A_N. 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 A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000. Each of the next Q lines represents an operation. "C a b c" means adding c to each of A_a, A_a+1, ... , A_b. -10000 ≤ c ≤ 10000. "Q a b" means querying the sum of A_a, A_a+1, ... , A_b.

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.

线段树区间修改区间查询

#include<cstdio> #include<utility> #include<iostream> using namespace std; #define _max 100010 int N, M; char c; pair<long long,long long> Seg [_max<<2];//每个点有两个属性，总数和lazy void Build_tree (int p, int l, int r) { if(l==r){ scanf("%lld",&Seg[p].first); return; } int mid = (l+r)>>1; Build_tree(2*p, l, mid); Build_tree(2*p+1, mid+1, r); Seg[p].first = Seg[2*p].first + Seg[2*p+1].first ; } /*******把lazy值往下传递*******/ /****p是父节点，q是父节点的长度****/ void Push_down (int p,int q) { Seg[2*p].first += (q-q/2)*Seg[p].second; Seg[2*p+1].first += q/2*Seg[p].second; if(q>1){//不是最底层节点，更新lazy值 Seg[2*p].second += Seg[p].second; Seg[2*p+1].second += Seg[p].second; } Seg[p].second = 0;//lazy值清零 } void Add (int p, int l, int r, int x, int y, int z) { /*******区间被整个覆盖，更改不急着传递到点，保存在这一层的lazy中*******/ if(l>=x && r<=y){ if(r-l>0) Seg[p].second += z ; Seg[p].first += z*(r+1-l) ;//这一点的和等于 增加数*点数（距离） return; } /*******区间没被完全覆盖，首先要把已有的lazy值传递下去*******/ if(Seg[p].second) Push_down(p,r-l+1); int mid = (l+r)>>1 ; if(x<=mid) Add(2*p, l, mid, x, y, z); if(y>mid) Add(2*p+1, mid+1, r, x, y, z); Seg[p].first = Seg[2*p].first + Seg[2*p+1].first; } long long Query (int p, int l, int r, int x, int y) { if(l>=x && r<=y) return Seg[p].first; /*******区间没被完全覆盖，先把lazy值传递下去*******/ if(Seg[p].second) Push_down(p,r-l+1); int mid = (l+r)>>1; long long ans = 0; if(x<=mid) ans += Query(2*p, l, mid, x, y); if(y> mid) ans += Query(2*p+1, mid+1, r, x, y); return ans; } int main () { scanf("%d%d",&N,&M); Build_tree(1, 1, N); for(int i=1; i<=M; i++){ scanf(" %c",&c); if(c=='C'){ int x, y, z; scanf("%d%d%d",&x,&y,&z); Add(1,1,N,x,y,z); } if(c=='Q'){ int x, y; scanf("%d%d",&x,&y); printf("%I64d\n", Query(1,1,N,x,y) ); } } return 0; }