HDU 1698 Just a Hook

思路：线段树操作区域覆盖
每个线段树的结点，存储该结点所代表区间的金属c，如果该区间全为同样的材料，
则用一个正数表示，如果含有多种材料，则用-1表示，每次执行替换操作时，如果
所要替换的材料与区间材料一样，则停止，如果所要替换区间跟当前结点区间一致，
则直接将所要替换材料赋给当前结点的c,否则，如果当前结点区间不是混合材料，
则先将当前结点的材料赋给左右子结点的c,并递归下去。

[cpp]
#include<iostream>
#include<stdio.h>
#define N 100010
struct node
{
   int l,r;
   int c;
}line[4*N];
void create(int k,int x,int y)
{
   line[k].l=x;
   line[k].r=y;
   line[k].c=1;
   if(x==y) return;
   int mid=(x+y)>>1;
   create(k<<1,x,mid);
   create(k<<1|1,mid+1,y);
}
void change(int k,int x,int y,int val)
{
   if(line[k].c==val) return;
   if(line[k].l==x&&line[k].r==y)
   {
      line[k].c=val;return;
   }
   if(line[k].c!=-1) line[k<<1].c=line[k<<1|1].c=line[k].c;
   line[k].c=-1;
   if(x>=line[k<<1|1].l) change(k<<1|1,x,y,val);
   else if(y<=line[k<<1].r) change(k<<1,x,y,val);
   else change(k<<1,x,line[k<<1].r,val),
    change(k<<1|1,line[k<<1|1].l,y,val);
}
int count(int k,int x,int y)
{
    if(line[k].c>0) return (y-x+1)*line[k].c;
    int mid=(line[k].l+line[k].r)>>1;
    return count(k<<1,x,mid)+count(k<<1|1,mid+1,y);
}
int main()
{
int T,n,m,a,b,c,i,tb=1;
scanf("%d",&T);
while(T--)
{
     scanf("%d%d",&n,&m);
     create(1,1,n);
     for(i=1;i<=m;i++)
     {
        scanf("%d%d%d",&a,&b,&c);
        change(1,a,b,c);
     } www.zzzyk.com
     printf("Case %d: The total value of the hook is %d.\n",tb++,count(1,1,n));
}
   return 0;
}

补充：软件开发 , C++ ,