這道題給我的教訓是：對于線段樹的更新一定要細心再細心！明確結點保存的信息，充分利用，考慮周到之后再動手編程！
以下是我的代碼：
#include<stdio.h>
#define maxn 100007
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
typedef __int64 Long;
typedef struct
{
long a,b;
Long add,sum;
bool cover;
}Node;
Node seg[maxn*4];
long n,q,r[maxn];
void build(long node,long x,long y)
{
long mid=(x+y)>>1;
seg[node].a=x;seg[node].b=y;
seg[node].add=0;seg[node].cover=false;
if(x==y)
seg[node].sum=r[x];
else
{
build(L(node),x,mid);
build(R(node),mid+1,y);
seg[node].sum=seg[L(node)].sum+seg[R(node)].sum;
}
}
void update(long node)
{
if(seg[node].cover)
{
seg[L(node)].sum+=(seg[L(node)].b-seg[L(node)].a+1)*seg[node].add;
seg[R(node)].sum+=(seg[R(node)].b-seg[R(node)].a+1)*seg[node].add;
seg[L(node)].add+=seg[node].add;
seg[R(node)].add+=seg[node].add;
seg[L(node)].cover=seg[R(node)].cover=true;
seg[node].add=0;seg[node].cover=false;
}
}
void add(long node,long x,long y,long d)
{
long a=seg[node].a,b=seg[node].b,mid=(a+b)>>1;
if(x<=a&&b<=y)
{
seg[node].sum=seg[node].sum+(seg[node].b-seg[node].a+1)*d;
seg[node].add+=d;
seg[node].cover=true;
}
else
{
update(node);
if(mid>=x)
add(L(node),x,y,d);
if(mid+1<=y)
add(R(node),x,y,d);
seg[node].sum=seg[L(node)].sum+seg[R(node)].sum;
}
}
Long getsum(long node,long x,long y)
{
long a=seg[node].a,b=seg[node].b,mid=(a+b)>>1;
Long re=0;
if(x<=a&&b<=y)
re=seg[node].sum;
else
{
update(node);
if(mid>=x)
re+=getsum(L(node),x,y);
if(mid+1<=y)
re+=getsum(R(node),x,y);
seg[node].sum=seg[L(node)].sum+seg[R(node)].sum;
}
return re;
}
int main()
{
char cmd[maxn];
long a,b,c;
scanf("%ld%ld",&n,&q);
for(long i=1;i<=n;i++) scanf("%ld",&r[i]);
getchar();
build(1,1,n);
for(long i=1;i<=q;i++)
{
scanf("%s",cmd);
if(cmd[0]=='C')
{
scanf("%ld%ld%ld",&a,&b,&c);
add(1,a,b,c);
}
else
{
scanf("%ld%ld",&a,&b);
printf("%I64d\n",getsum(1,a,b));
}
}
return 0;
}
posted on 2010-03-15 23:02
lee1r 閱讀(150)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構