学步园

题意：在一组数中执行两种操作
"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.

思路：很典型的线段树 开始我用普通的线段树做 updata 操作是每一对应的区间都加上w 结果TLE
问了一下zcube 说用什么 线段树遗传（不明白这是个什么？？） 上网看了一下别人的解题报告 updata
操作的复杂度太高了（因为我要遍历所有要更新的点 时间复杂度是多少 我不会算
望大牛指点） 然后加了一下优化

//6720K   
1579MS

#include <stdio.h>
#define M 100005

struct data
{
    int
l,r;
    __int64
sum,add;   
//两个变量都要用__int64 因为这个WA了几次
} line[3*M];

int num[M];
__int64 ans;
void BuildTree (int left,int right,int u)
{
    line[u].l =
left;
    line[u].r =
right;
    line[u].add
= 0;
    if (left ==
right)
       
line[u].sum = num[left];
    else
    {
       
int mid = (line[u].l+line[u].r)/2;
       
BuildTree(left,mid,2*u);
       
BuildTree(mid+1,right,2*u+1);
       
line[u].sum = line[2*u].sum + line[2*u+1].sum;
    }
}

void updata (int left,int right,int w,int u)
{
    if
(line[u].l==left&&line[u].r==right)        
//区间一样，就退出 不做再遍历其下面的点 省
   
{                                               
//很多时间
       
line[u].add += w;
       
return ;
    }
    line[u].sum
+= (right-left+1)*w;
    int mid =
(line[u].l+line[u].r)/2;
    if (right
<= mid)
       
updata(left,right,w,2*u);
    else if
(left >= mid+1)
       
updata (left,right,w,2*u+1);
    else
    {
       
updata (left,mid,w,2*u);
       
updata (mid+1,right,w,2*u+1);
    }
}

void query (int left,int right,int u)
{
    ans +=
line[u].add*(right-left+1);
    int mid =
(line[u].l+line[u].r)/2;
    if
(line[u].l == left&&line[u].r ==
right)
       
ans += line[u].sum;
    else if
(right <= mid)
       
query(left,right,2*u);
    else if
(left >= mid+1)
       
query(left,right,2*u+1);
    else
    {
       
query(left,mid,2*u);