题意：给你一列不同材质金属棒（金，银，铜），不同的材质价值不同（金-3，银-2，铜-1），起初金属棒全是铜的。对这些金属棒进行一系列的更换后问你全部的金属棒的总价值。
题解：线段树+lazy。
第一次我竟然写成了这样的。。。
printf("Case %d: The total value of the hook is %d.\n",++cas,val[1]); 显然这是错误的！粗心了啊。。。正确的应是：
printf("Case %d: The total value of the hook is %d.\n",++cas,Query(1,n,1,n,1)); 还有最后的那个“.”（句号）与应输出的数字之间没有空格！
AC代码：
View Code 1 #include2 #include 3 using namespace std; 4 const int maxn=10000000; 5 int val[maxn],change[maxn]; 6 void Build(int l,int r,int pos){ 7 change[pos]=0; 8 if(l==r){ 9 val[pos]=1;10 return;11 }12 int mid=(l+r)>>1;13 Build(l,mid,pos*2);14 Build(mid+1,r,pos*2+1);15 val[pos]=val[pos*2]+val[pos*2+1];16 }17 void PushDown(int pos,int num){18 if(change[pos]){19 change[pos*2]=change[pos];20 change[pos*2+1]=change[pos];21 val[pos*2]=change[pos]*(num-(num>>1));22 val[pos*2+1]=change[pos]*(num>>1);23 change[pos]=0;24 }25 }26 void Updata(int l,int r,int z,int left,int right,int pos){27 if(l<=left&&right<=r){28 val[pos]=(right-left+1)*z;29 change[pos]=z;30 return;31 }32 PushDown(pos,right-left+1);33 int mid=(left+right)>>1;34 if(r<=mid)Updata(l,r,z,left,mid,pos*2);35 else if(l>mid)Updata(l,r,z,mid+1,right,pos*2+1);36 else{37 Updata(l,r,z,left,mid,pos*2);38 Updata(l,r,z,mid+1,right,pos*2+1);39 }40 val[pos]=val[pos*2]+val[pos*2+1];41 }42 int Query(int l,int r,int left,int right,int pos){43 if(l<=left&&right<=r)return val[pos];44 PushDown(pos,right-left+1);45 int mid=(left+right)>>1;46 if(r<=mid)return Query(l,r,left,mid,pos*2);47 if(l>mid)return Query(l,r,mid+1,right,pos*2+1);48 int lval=Query(l,r,left,mid,pos*2);49 int rval=Query(l,r,mid+1,right,pos*2+1);50 return lval+rval;51 }52 int main()53 {54 int T,cas=0,Q,x,y,z,n;55 scanf("%d",&T);56 while(T--){57 scanf("%d",&n);58 Build(1,n,1);59 scanf("%d",&Q);60 while(Q--){61 scanf("%d %d %d",&x,&y,&z);62 Updata(x,y,z,1,n,1);63 }64 printf("Case %d: The total value of the hook is %d.\n",++cas,Query(1,n,1,n,1));65 }66 return 0;67 }