A Simple Problem with Integers

Time Limit: 5000MS Memory Limit: 131072K

Total Submissions: 108903 Accepted: 33919

Case 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₊₁, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a₊₁, ... , 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

Hint

The sums may exceed the range of 32-bit integers.

Source

POJ Monthly--2007.11.25, Yang Yi

带lazy的线段树

 //2017-05-17

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define ll long long

 #define mid ((st[id].l+st[id].r)>>1)

 #define lson (id<<1)

 #define rson ((id<<1)|1)

 using namespace std;

 const ll N = ;

 ll arr[N];

 struct Node{

     ll l, r, sum, lazy;

 }st[N<<];

 void build(int id, int l, int r)

 {

     st[id].l = l; st[id].r = r; st[id].lazy = ;

     if(l == r){

         st[id].sum = arr[l];

         return;

     }

     build(lson, l, mid);

     build(rson, mid+, r);

     st[id].sum = st[lson].sum+st[rson].sum;

 }

 void push_down(int id)

 {

     if(st[id].lazy != ){

         st[lson].lazy += st[id].lazy;

         st[rson].lazy += st[id].lazy;

         st[id].sum += (st[id].r-st[id].l+)*st[id].lazy;

         st[id].lazy = ;

     }

     return;

 }

 ll query(int id, int l, int r)

 {

     if(st[id].l == l && st[id].r == r)return st[id].sum+(r-l+)*st[id].lazy;

     push_down(id);

     if(r <= mid)return query(lson, l, r);

     else if(l > mid)return query(rson, l, r);

     else return query(lson, l, mid)+query(rson, mid+, r);

 }

 void update(int id, int l, int r, int w)

 {

     if(st[id].l == l && st[id].r == r){

         st[id].lazy += w;

         return;

     }

     st[id].sum += (r-l+)*w;

     if(r <= mid)update(lson, l, r, w);

     else if(l > mid)update(rson, l, r, w);

     else{

         update(lson, l, mid, w);

         update(rson, mid+, r, w);

     }

 }

 int main()

 {

     ll n, q;

     while(scanf("%lld%lld", &n, &q)!=EOF){

         for(int i = ; i <= n; i++)

           scanf("%lld", &arr[i]);

         build(, , n);

         char op[];

         ll a, b, c;

         while(q--){

             scanf("%s", op);

             if(op[] == 'Q'){

                 scanf("%lld%lld", &a, &b);

                 printf("%lld\n", query(, a, b));

             }else if(op[] == 'C'){

                 scanf("%lld%lld%lld", &a, &b, &c);

                 update(, a, b, c);

             }

         }

     }

     return ;

 }

 //2018-03-28

 import java.util.*;

 public class Main {

     public static void main(String[] args) {

         Scanner cin = new Scanner(System.in);

         int n, q;

         while(cin.hasNext()) {

             n = cin.nextInt();

             q = cin.nextInt();

             SegmentTree st = new SegmentTree(n);

             for(int i = 1; i <= n; i++)

                 st.arr[i] = cin.nextLong();

             st.build(1, 1, n);

             char op;

             int a, b;

             long c;

             while(q-- > 0) {

                 op = cin.next().charAt(0);

                 if(op == 'Q') {

                     a = cin.nextInt();

                     b = cin.nextInt();

                     System.out.println(st.query(1, a, b));

                 }else if(op == 'C') {

                     a = cin.nextInt();

                     b = cin.nextInt();

                     c = cin.nextLong();

                     st.updata(1, a, b, c);

                 }

             }

         }

     }

 }

 class SegmentTree{

     static class Node{

         public int l, r;

         long sum, lazy;

         Node(int _l, int _r, long _sum, long _lazy){

             this.l = _l;

             this.r = _r;

             this.sum = _sum;

             this.lazy = _lazy;

         }

     }

     public int n;

     public long [] arr;

     public Node [] nodes;

     SegmentTree(int _n){

         this.n = _n;

         arr = new long[n+1];

         nodes = new Node[n<<2];

     }

     int lson(int id) {

         return (id<<1);

     }

     int rson(int id) {

         return ((id<<1)|1);

     }

     int mid(int id) {

         return (nodes[id].l + nodes[id].r)>>1;

     }

     void build(int id, int l, int r) {

         nodes[id] = new Node(l, r, 0, 0);

         if(l == r) {

             nodes[id].sum = arr[l];

             return;

         }

         build(lson(id), l, mid(id));

         build(rson(id), mid(id)+1, r);

         nodes[id].sum = nodes[lson(id)].sum + nodes[rson(id)].sum;

     }

     void pushDown(int id) {

         if(nodes[id].lazy != 0) {

             nodes[lson(id)].lazy += nodes[id].lazy;

             nodes[rson(id)].lazy += nodes[id].lazy;

             nodes[id].sum += (nodes[id].r-nodes[id].l+1)*nodes[id].lazy;

             nodes[id].lazy = 0;

         }

     }

     long query(int id, int l, int r) {

         if(nodes[id].l == l && nodes[id].r == r)

             return nodes[id].sum+(r-l+1)*nodes[id].lazy;

         pushDown(id);

         if(r <= mid(id))return query(lson(id), l, r);

         else if(l > mid(id))return query(rson(id), l, r);

         else return query(lson(id), l, mid(id))+query(rson(id), mid(id)+1, r);

     }

     void updata(int id, int l, int r, long w) {

         if(nodes[id] == null)return;

         if(nodes[id].l == l && nodes[id].r == r) {

             nodes[id].lazy += w;

             return;

         }

         nodes[id].sum += (r-l+1)*w;

         if(r <= mid(id))updata(lson(id), l, r, w);

         else if(l > mid(id))updata(rson(id), l, r, w);

         else {

             updata(lson(id), l, mid(id), w);

             updata(rson(id), mid(id)+1, r, w);

         }

     }

 }

巴特西

POJ3468(KB7-C 线段树)