Time Limit:5000MS   Memory Limit:131072K

Case Time Limit:2000MS

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.

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.

You need to answer all Q commands in order. One answer in a line.

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

4

55

9

15

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

 

题解：本题也是线段树系列的模板题之一，要求的是成段更新+懒惰标记。PS：原题的说明有问题，上面说的“C a b c”中的c的范围其实在int32之外，需要使用long long，否则定是WA，真心坑爹，连WA多次，还是在discuss中看到的原因。

 

稍微讲解下代码中的一些细节: step<<1 与 step<<1|1，意思分别是step*2 和step*+1，具体为什么，可以回去复习一下位运算

 

转自 http://www.cnblogs.com/kevince/p/3888608.html

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<map>

 #define N 100010

 #define M 15

 #define mod 1000000007

 #define mod2 100000000

 #define ll long long

 #define maxi(a,b) (a)>(b)? (a) : (b)

 #define mini(a,b) (a)<(b)? (a) : (b)

 using namespace std;

 int n,q;

 int x[N];

 char ch;

 int a,b,c;

 struct node

 {

     ll mark,sum;

 }tree[*N];

 void update(int l,int r,int i)

 {

     if(!tree[i].mark) return;

     int mid=(l+r)/;

     tree[*i].sum+=tree[i].mark*(ll)(mid-l+);

     tree[*i+].sum+=tree[i].mark*(ll)(r-mid);

     tree[*i].mark+=tree[i].mark;

     tree[*i+].mark+=tree[i].mark;

     tree[i].mark=;

 }

 ll query(int tl,int tr,int l,int r,int i)

 {

     if(tl>r || tr<l)

         return ;

     if(tl<=l && r<=tr)

         return tree[i].sum;

     update(l,r,i);

     int mid=(l+r)/;

     return query(tl,tr,l,mid,*i)+query(tl,tr,mid+,r,*i+);

 }

 void addd(int tl,int tr,int l,int r,int i,int val)

 {

     if(tl>r || tr<l)

         return;

     if(tl<=l && tr>=r){

         tree[i].sum+=val*(ll)(r-l+);

         tree[i].mark+=val;

         return;

     }

     update(l,r,i);

     int mid=(l+r)/;

     addd(tl,tr,l,mid,*i,val);

     addd(tl,tr,mid+,r,*i+,val);

     tree[i].sum=tree[*i].sum+tree[*i+].sum;

 }

 void build_tree(int l,int r,int i)

 {

     if(l==r){

         tree[i].sum=x[l];

         return;

     }

     int mid=(l+r)/;

     build_tree(l,mid,*i);

     build_tree(mid+,r,*i+);

     tree[i].sum=tree[*i].sum+tree[*i+].sum;

 }

 int main()

 {

     int i;

    // freopen("data.in","r",stdin);

     //scanf("%d",&T);

     //for(int cnt=1;cnt<=T;cnt++)

     //while(T--)

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

     {

        // printf(" %d %d \n",n,q);

        for(i=;i<=n;i++) scanf("%d",&x[i]);

       // printf(" 1\n");

        memset(tree,,sizeof(tree));

        build_tree(,n,);

       //  printf(" 2\n");

        getchar();

        while(q--){

           //  printf(" 3\n");

             scanf("%c",&ch);

           //  printf(" %c\n",ch);

             if(ch=='C'){

                 //printf(" 31\n");

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

                 getchar();

                 addd(a,b,,n,,c);

             }

             else{

                   //  printf(" 32\n");

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

                 getchar();

                 ll ans=query(a,b,,n,);

                 printf("%I64d\n",ans);

             }

        }

     }

     return ;

 }