HU-698-Just a Hook
1727 ワード
HU-698-Just a Hook
http://acm.hdu.edu.cn/showproblem.php?pid=1698
線分樹をセグメントごとに更新しますか?
http://acm.hdu.edu.cn/showproblem.php?pid=1698
線分樹をセグメントごとに更新しますか?
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 100005
struct cam
{
int x;
int y;
int sum;
int val;
}list[N*4];
void build(int k,int x,int y)
{
int mid;
list[k].x=x;
list[k].y=y;
list[k].val=1;
if(list[k].x==list[k].y)
{
list[k].sum=1;
return;
}
mid=(x+y)/2;
build(k<<1,x,mid);
build(k<<1|1,mid+1,y);
list[k].sum=list[k<<1].sum+list[k<<1|1].sum;
}
void update(int k,int x,int y,int d)
{
int mid;
if(list[k].x==x&&list[k].y==y)
{
list[k].val=d;
list[k].sum=(list[k].y-list[k].x+1)*list[k].val;
return;
}
if(list[k].val!=0)
{
list[k<<1].sum=(list[k<<1].y-list[k<<1].x+1)*list[k].val;
list[k<<1|1].sum=(list[k<<1|1].y-list[k<<1|1].x+1)*list[k].val;
list[k<<1].val=list[k].val;
list[k<<1|1].val=list[k].val;
list[k].val=0;
}
mid=(list[k].x+list[k].y)/2;
if(x>mid)
update(k<<1|1,x,y,d);
else if(y<=mid)
update(k<<1,x,y,d);
else
{
update(k<<1,x,mid,d);
update(k<<1|1,mid+1,y,d);
}
list[k].sum=list[k<<1].sum+list[k<<1|1].sum;
}
int main()
{
int t,a,b,c;
int n,m,i;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
scanf("%d",&n);
build(1,1,n);
scanf("%d",&m);
while(m--)
{
scanf("%d %d %d",&a,&b,&c);
update(1,a,b,c);
}
printf("Case %d: The total value of the hook is %d.
",i,list[1].sum);
}
return 0;
}