学步园

原题连接：http://poj.org/problem?id=3468

题意：略……

思路：注意  区间值改变时 有负数，数据范围比较大，int 会溢出。。这题就是一个入门的线段数 插线问线问题。刚学习线段数  WR 了很久……

代码：

#include<stdio.h>
#include<string.h>
#define Max 4*100000
#define Mid(x,y) (x+y)>>1  //(x+y)/2
__int64 A[Max],cnt;
__int64 ans;
struct hello
{
    int l;
    int r;
    __int64 loop;  //注意，int就错了！！！！
    __int64 sum;
}tree[Max];
void Build_tree(int l,int r,int t)  // l,r 表示区间，t表示 区间节点
{
    int x;
    tree[t].l=l;
    tree[t].r=r;
    tree[t].loop=0;
    tree[t].sum=0;
    if(l==r)
    {
        while(t)
        {
            tree[t].sum+=A[l];
            t/=2;
        }
        return ;
    }
    x=Mid(l,r);
    Build_tree(l,x,2*t);
    Build_tree(x+1,r,2*t+1);
}
void Updata_tree(int l,int r,int t)
{
    if(tree[t].l==l&&tree[t].r==r)
    {
        tree[t].loop+=cnt;
        int y=cnt*(tree[t].r-tree[t].l+1);
        while(t)
        {
            tree[t].sum+=y;
            t/=2;
        }
        return ;
    }
    int x=Mid(tree[t].l,tree[t].r);
    if(tree[t].loop)
    {
        tree[t*2].loop+=tree[t].loop;              //更新标记，向下传递！！
        tree[t*2+1].loop+=tree[t].loop;
        tree[t*2].sum+=tree[t].loop*(tree[2*t].r-tree[t*2].l+1);
        tree[t*2+1].sum+=tree[t].loop*(tree[t*2+1].r-tree[t*2+1].l+1);
        tree[t].loop=0;
    }
    if(x>=r)
      Updata_tree(l,r,2*t);
    else if(x+1<=l)
      Updata_tree(l,r,2*t+1);
    else
    {
        Updata_tree(l,x,2*t);
        Updata_tree(x+1,r,2*t+1);
    }
}
void Query_tree(int l,int r,int t)
{
    if(tree[t].l==l&&tree[t].r==r)
    {
        ans+=tree[t].sum;
        return ;
    }
    if(tree[t].loop)
    {
        tree[t*2].loop+=tree[t].loop;              //更新标记，向下传递！！
        tree[t*2+1].loop+=tree[t].loop;
        tree[t*2].sum+=tree[t].loop*(tree[2*t].r-tree[t*2].l+1);
        tree[t*2+1].sum+=tree[t].loop*(tree[t*2+1].r-tree[t*2+1].l+1);
        tree[t].loop=0;
    }

    int x=Mid(tree[t].l,tree[t].r);
    if(x>=r)
      Query_tree(l,r,2*t);
    else if(x+1<=l)
      Query_tree(l,r,2*t+1);
    else
    {
        Query_tree(l,x,2*t);
        Query_tree(x+1,r,2*t+1);
    }
}
int main()
{
    int i,j,n,m,ncase,q;
    while(~scanf("%d%d",&n,&q))
    {
        for(i=1;i<=n;i++)
          scanf("%I64d",&A[i]);
        Build_tree(1,n,1);
        while(q--)
        {
           char ch[10];
           scanf("%s",ch);
           if(ch[0]=='C')
           {
               scanf("%d%d%I64d",&i,&j,&cnt);//i,j 区间增加每点 cnt;
               Updata_tree(i,j,1);
           }
           else if(ch[0]=='Q')
           {
               ans=0;
               scanf("%d%d",&i,&j);
               Query_tree(i,j,1);
               printf("%I64d\n",ans);
           }
       }
    }

}