题意 ： 一个有n段长的金属棍，开始都涂上铜，分段涂成别的，金的值是3，银的值是2，铜的值是1，然后问你最后这n段总共的值是多少。
思路 : 线段树的区间更新。可以理解为线段树成段更新的模板题。
//HDU 1698
#include <cstdio>
#include <cstring>
#include <iostream> using namespace std; int lz[],p[] ; //lz延迟标记，每次更新不需要更新到底，使得更新延迟到下次更新或者查询的时候
void pushdown(int rt,int m)
{
if(lz[rt])
{
lz[rt << ] = lz[rt] ;
lz[rt << | ] = lz[rt] ;
p[rt << ] = (m -( m >> )) * lz[rt] ;
p[rt << | ] = (m>>) * lz[rt] ;
lz[rt] = ;
}
}
void pushup(int rt) // 将左右孩子的值更新到自己
{
p[rt] = p[rt << ] + p[rt << | ] ;
} void update(int L,int R,int l,int r,int sc,int rt)
{
if(l >= L && r <= R)
{ lz[rt] = sc ;
p[rt] = (r-l+)*sc ;
return ;
}
pushdown(rt,r-l+) ;
int m = (r + l ) >> ;
if(m >= L)
update(L,R,l,m,sc,rt << ) ;
if(R > m)
update(L,R,m+,r,sc,rt << | ) ;
pushup(rt) ;
}
void build(int l,int r,int rt)
{
lz[rt] = ;
if(l == r)
{
p[rt] = ;
return ;
}
int mid = (l + r) >> ;
build(l,mid,rt << ) ;
build(mid + ,r,rt << | ) ;
pushup(rt) ;
}
int query(int L,int R,int l,int r,int rt)
{
int sum = ;
if(L <= l && r <= R)
{ return p[rt] ;
}
pushdown(rt , r-l+) ;
int mid = (l + r) >> ;
if(mid >= L)
sum += query(L,R,l,mid,rt << ) ;
if(mid < R)
sum += query(L,R,mid+,r,rt << | ) ;
return sum ; }
int main()
{
int T,N,Q ;
cin >> T ;
int casee = ;
while(T--)
{
int x,y,z ;
cin >> N >> Q ;
build(,N,) ;
while(Q--)
{
cin >> x >> y >> z ;
update(x,y,,N,z,) ;
}
int sum = query(,N,,N,) ;
cout<<"Case "<< casee ++ <<": The total value of the hook is "<<sum <<"."<<endl ;
}
return ;
}