题目连接：
http://acm.hdu.edu.cn/showproblem.php?pid=1698
题目大意：
有一个钩子有n条棍子组成，棍子有铜银金三种组成，价值分别为1,2,3。为了对付每场战斗需要对组成钩子某个区间的棍子进行调整。问经过q次调整后钩子的总价值是多少？
解题思路：
线段树更新。因为数据范围的问题，每次更新到节点会TLE。用区间更新就会节省很多的时间，对每一个区间来讲，如果这个区间里面的棍子都是相同类型的，就用一个节点变量记录棍子类型，如果区间内棍子是不同类型，则将变量记录为-1。
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int manx = ;
struct node
{
int l, r, x;
int Mid()
{
return (l+r)/;
}
} tree[manx];
void build (int root, int l, int r)
{//建树，棍子都为铜质
tree[root].l = l;
tree[root].r = r;
tree[root].x = ;
if (l == r)
return ;
build (*root+, l, tree[root].Mid());
build (*root+, tree[root].Mid()+, r);
}
void update (int root, int l, int r, int s)
{
if (tree[root].l==l && tree[root].r==r)
{//当前区间都为s类型的棍子
tree[root].x = s;
return ;
}
else if (tree[root].x != -)
{//当前区间棍子并不一样，需要把当前区间的状态转移到左右子树并标记当前区间
tree[*root+].x = tree[*root+].x = tree[root].x;
tree[root].x = -;
}
if (r <= tree[root].Mid())
update (*root+, l, r, s);
else if (l > tree[root].Mid())
update (*root+, l, r, s);
else
{
update (*root+, l, tree[root].Mid(), s);
update (*root+, tree[root].Mid()+, r, s);
}
}
int Sum (int root, int l, int s)
{
if (tree[root].x != -)//当前区间棍子类型一样，则不再向下查询
return tree[root].x * (s - l + );
else
{
return Sum(*root+, l, tree[root].Mid()) + Sum(*root+, tree[root].Mid()+, s);
}
}
int main ()
{
int t, l = ;
scanf ("%d", &t);
while (t --)
{
int n, q;
scanf ("%d %d", &n, &q);
build (, , n);
while (q --)
{
int a, b, x;
scanf ("%d %d %d", &a, &b, &x);
update (, a, b, x);
}
int res = Sum(, , n);
printf ("Case %d: The total value of the hook is %d.\n", ++l, res);
}
return ;
}