#include<iostream>
#define Inf 400001

#define Maxt 100050
using namespace std;

int N,Q;
int date[Maxt];

struct node 
{
    int left,right;
    long long  cover;
    long long  mmd;
    long long  sum;
}Tree[Inf];

void biuld_tree(int nums, int begin , int end)
{
     Tree[nums].left = begin;
     Tree[nums].right = end;
     Tree[nums].cover = 0;
     Tree[nums].mmd = 0;
     Tree[nums].sum = date[end] - date[begin -1];
     if( begin == end) return ;
     int mid = ( begin + end) >> 1;
     biuld_tree( ( nums << 1) , begin , mid);
     biuld_tree( ( nums << 1) + 1 , mid + 1 , end);
}

long long find_Q(int nums , int begin ,int end , long long t)
{
   
    if( Tree[nums].left == begin && end == Tree[nums].right)
    {
          return ( Tree[nums].sum + Tree[nums].cover + t);
    }
    int mid = ( Tree[nums].left + Tree[nums].right) >> 1;
    if( end <= mid)
    {
        return find_Q( ( nums << 1) , begin , end , t + Tree[nums].mmd);
    }
    else if( begin > mid)
    {
        return find_Q(( nums << 1) + 1 , begin , end ,t + Tree[nums].mmd);
    }
    else return ( find_Q((nums << 1) , begin ,mid , t + Tree[nums].mmd)) + ( find_Q(( nums << 1) + 1 , mid + 1 , end , t + Tree[nums].mmd));
}
void update_c( int nums , int begin ,int end , long long int n)
{
    if( Tree[nums].left == begin && Tree[nums].right == end)
    {
        Tree[nums].cover += n * ( end - begin + 1);
        Tree[nums].mmd += n;
        return ;
    }
    
    int mid = ( Tree[nums].left + Tree[nums].right) >> 1;
    Tree[nums].cover += ( end - begin + 1) * n;
    if( end <= mid)
    {
        update_c( ( nums << 1 ) , begin , end , n);
    }
    else if( begin > mid)
    {
        update_c(( nums << 1) + 1 , begin , end , n);
    }
    else
    {
        update_c(( nums << 1)  , begin , mid , n);
        update_c((nums << 1) + 1 , mid + 1 , end , n);
    }
}

void out()
{
    int i;
    for(  i = 1 ; i <= 20 ; ++i) 
    cout << Tree[i].left << " " << Tree[i].right << " " 
    << Tree[i].cover << " " << Tree[i].sum << "  " << Tree[i].mmd <<  endl; 
    cout << " =================  tree over ================= " << endl;
}
void date_in()
{
    int i;
    cin >> N >> Q;
    int d;
    date[0] = 0;
    for( i = 1 ; i <= N ; ++i)
    {
        scanf("%d",&d);
        date[i] = date[i -1] + d;
    }
    biuld_tree(1 , 1 , N);
    char cc;
    scanf("%c",&cc);
    int a,b,c;
    for( i = 1 ; i <= Q ; ++i)
    {
        scanf("%c",&cc);
        
        if( cc == 'Q')
        {
             scanf("%d %d",&a,&b);
             cout << find_Q(1 ,a , b , 0) << endl;
        }
        else if( cc == 'C')
        {
             scanf("%d %d %d",&a,&b,&c);
             update_c( 1 , a , b , c);
        }
        scanf("%c",&cc);
    }
}
int main()
{
  // freopen("acm.in","r",stdin);
    date_in();
    return 0;
}

• Re:POJ　3468 why wa ? 　 (14) fanxicai2001 2009-04-27 14:44:44