POJ 3468(線分樹＋遅延更新)

A Simple Proble with Integers
Time Limit:5000 MS
 
メモリLimit:13131313722 K
Total Submissions:43776
 
Acceepted:12806
Case Time Limit:2000 MS
Description
You have N integers,A 1,A 2,…,AN.You need to deal with two kinds of operation.One type of operation is to add some given to each number.The other is to ask for the sum of nbers.inven.inven.given.
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 1,A 2,...AN.-100000≦Ai≦100000 000 000.Each of the nexxt line Q inininesents s rerereesents+1.aapaneneinininininininininininininininininininininininininininininininininininininininininininininininininents+1.aatos+1.atos+1.aaaaatos+1.aaaasum of Aa,Aa＋1,…,Ab.
Output
You need to answer all Q command 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

//        ，                     ！   add          ，           ，         ！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define MAX 100003
typedef __int64 ll;
ll da[MAX],ans;
struct node 
{
 ll left,right,add;
 ll sum;
}tree[MAX*4];
//   left,right     ，   a          1   tree   
void build( ll id, ll left, ll right )
{
 tree[id].add=0;
    tree[id].left = left;
 tree[id].right = right;
    if( left == right )
    {
        tree[id].sum = da[left];
  return ;
    }
    else
    {
        ll mid = ( left + right )>>1;        
        build( id <<1, left, mid );
        build( id<<1|1, mid + 1, right );
        tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum;
 }
}
//  
void updata( ll id, ll left, ll right, ll adi)
{
 if(tree[id].left==left&&tree[id].right==right)
 {
  tree[id].add+=adi;
  return ;
 }
 else 
 {
  if(tree[id].add!=0)
  {
   tree[id].sum+=(tree[id].right-tree[id].left+1)*tree[id].add;
   tree[id<<1].add+=tree[id].add;
   tree[id<<1|1].add+=tree[id].add;
   tree[id].add=0;
  }
  tree[id].sum+=( right-left+1)*adi;
  
  ll mid=(tree[id].left+tree[id].right)>>1;
  if(right<=mid)
   updata(id<<1,left,right,adi);
  else if(left>mid)
   updata(id<<1|1,left,right,adi);
  else
  {
   updata(id<<1,left,mid,adi);
   updata(id<<1|1,mid+1,right,adi);
  }
 }
}
//3.  
//*****************************************************************
void query(ll id, ll left, ll right)
{
    if( tree[id].left==left&&tree[id].right== right)
    {
  if(tree[id].add==0)
  {
   ans+=tree[id].sum;
   return ;
  }
  else
  {
   ans+=tree[id].sum+(tree[id].right-tree[id].left+1)*tree[id].add;
   return ;
  }
    }
 else
 {
  if(tree[id].add!=0)
  {
   tree[id].sum+=(tree[id].right-tree[id].left+1)*tree[id].add;
   tree[id<<1].add+=tree[id].add;
   tree[(id<<1)+1].add+=tree[id].add;
   tree[id].add=0;
   
  }
  ll mid = (tree[id].left+tree[id].right)>>1;
  if(right<= mid )
   query( id <<1, left,right);
  else if(left>mid  )
   query( (id <<1)+ 1,left, right);
  else 
  {
   query( id <<1,  left,mid);
   query( (id<<1) + 1, mid+1,right );
  }
 }
}
int main()
{
 ll n,i,m;
 scanf("%I64d%I64d",&n,&m);
 //while(~scanf("%d%d",&n,&m))
// {
  for(i=1;i<=n;i++)
   scanf("%I64d",&da[i]);
  
  build(1,1,n);
  for(i=0;i<m;i++)
  {
   ll a,b,c;
   char op;
   scanf(" %c",&op);
   if(op=='C')
   {
    scanf("%I64d%I64d%I64d",&a,&b,&c);
    updata(1,a,b,c);
   }
   else if(op=='Q')
   {
    ans=0;
    scanf("%I64d%I64d",&a,&b);
    query(1, a,b);
    printf("%I64d
",ans);
   }
  }
 //}
 return 0;
}