2017-08-30 18:54:40
writer：pprp
可以跟上一篇博客做个对比，
这种实现不是很好理解，上一篇比较好理解，但是感觉有的地方不够严密
代码如下：
/*
@theme:segmentation/interval T
@writer:pprp
@begin:15:26
@end:16:13
@declare: 使用lazy标记的线段树,HDU 1698
这次写的是带结构体的那种
@date:2017/8/30
*/ #include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib> using namespace std;
const int maxn = ; struct tree
{
int r, l;
int v; //lazy标记
int mid;//中间的值
} T[maxn<<]; //test:ok
void pushDown(int rt)
{
T[rt<<].v = T[rt<<|].v = T[rt].v;
T[rt].v = -; //-1代表着
} //void build(int rt, int l, int r)
//{
// T[rt].l = l, T[rt].r = r;
// T[rt].v = 1; //因为这个题中认为每个节点的值都是1
// T[rt].mid = (l+r)>>1;
// if(l == r)return ;
// //递归求解对两边进行处理
// build(rt<<1,l,T[rt].mid);
// build(rt<<1|1,T[rt].mid+1,r);
//} void build(int rt,int L,int R)
{
T[rt].l=L,T[rt].r=R;T[rt].mid = (L+R)>>;
T[rt].v=;
if(L==R){return;}
build(rt<<,L,T[rt].mid);
build(rt<<|,T[rt].mid+,R);
} void update(int rt, int L, int R, int z)
{
if(L <= T[rt].l && R >= T[rt].r) //error find
{
T[rt].v = z;
return;
}
else
{
if(T[rt].v != -) //如果不是-1也就是说之前没有被pushdown过，那就pushdown
pushDown(rt);
if(L > T[rt].mid)
update(rt<<|,L,R,z);
else if(R <= T[rt].mid)
update(rt<<,L,R,z);
else //左右都有
{
update(rt<<,L,T[rt].mid,z);
update(rt<<|,T[rt].mid+,R,z);
}
}
} //找到根节点的sum值
int Find(int rt)
{
//判断根节点是否有lazy标记
if(T[rt].v != -)
return T[rt].v * (T[rt].r-T[rt].l+);
else
return Find(rt<<) + Find(rt<<|);
} int main()
{
//freopen("in.txt","r",stdin);
int N,n,m,i,j,k,v,c=;
scanf("%d",&N);
while(N--)
{
scanf("%d %d",&n,&m);
build(,,n);
for(i=;i<=m;++i){
scanf("%d%d%d",&j,&k,&v);
update(,j,k,v);
}
printf("Case %d: The total value of the hook is %d.\n",++c,Find());
}
return ;
}