HDU-1698-Just a Hook
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.\n",i,list[1].sum);}return 0;
}
