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.2cto.com
     printf("Case %d: The total value of the hook is %d.\n",tb++,count(1,1,n)); 
  } 
   return 0; 
}