線段樹的成段更新與區(qū)間求和，注意更新時及時更新子結點的區(qū)間信息。
#include<stdio.h>
#define maxn 100007
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
struct
{
long a,b,sum,kind;
}seg[maxn*3];
long test,n,m;
void build(long node,long x,long y)
{
long mid=(x+y)>>1;
seg[node].a=x;seg[node].b=y;
seg[node].sum=seg[node].b-seg[node].a+1;
seg[node].kind=0;
if(x<y)
{
build(L(node),x,mid);
build(R(node),mid+1,y);
}
}
void insert(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].kind=d;
seg[node].sum=(seg[node].b-seg[node].a+1)*d;
}
else
{
if(seg[node].kind>0)
{
seg[L(node)].kind=seg[R(node)].kind=seg[node].kind;
seg[L(node)].sum=(seg[L(node)].b-seg[L(node)].a+1)*seg[L(node)].kind;
seg[R(node)].sum=(seg[R(node)].b-seg[R(node)].a+1)*seg[R(node)].kind;
seg[node].kind=0;
}
if(mid>=x)
insert(L(node),x,y,d);
if(mid+1<=y)
insert(R(node),x,y,d);
seg[node].sum=seg[L(node)].sum+seg[R(node)].sum;
}
}
int main()
{
scanf("%ld",&test);
for(long k=1;k<=test;k++)
{
scanf("%ld%ld",&n,&m);
build(1,1,n);
while(m--)
{
long a,b,d;
scanf("%ld%ld%ld",&a,&b,&d);
insert(1,a,b,d);
}
printf("Case %ld: The total value of the hook is %ld.\n",k,seg[1].sum);
}
return 0;
}
posted on 2010-02-24 17:24
lee1r 閱讀(391)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)據(jù)結構