原题
线段树区间修改模版，不会的百度一下线段树懒惰标记！
//hdu 1698 just a hook
#include
#include
#include
#define lson l,m,pos<<1
#define rson m+1,r,pos<<1|1
using namespace std;
int n,m,T;
int sum[6010000],col[6010000];
void pushup(int pos){sum[pos]=sum[pos<<1]+sum[pos<<1|1];
}
void pushdown(int pos,int len)
{
if (col[pos])
{
col[pos<<1]=col[pos<<1|1]=col[pos];
sum[pos<<1]=col[pos<<1]*(len-(len>>1));
sum[pos<<1|1]=col[pos<<1|1]*(len>>1);
col[pos]=0;
}
}
void build(int l,int r,int pos)
{
col[pos]=0;
if(l==r){sum[pos]=1;
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(pos);
}
void update(int L,int R,int add,int l,int r,int pos)
{
if(L<=l&&r<=R)
{
col[pos]=add;
//只有在更新的时候再打懒惰标记
sum[pos]=col[pos]*(r-l+1);
return;
}
pushdown(pos,r-l+1);
int m=(l+r)>>1;
if (L<=m) update(L,R,add,lson);
if (R>m) update(L,R,add,rson);
pushup(pos);
}int main()
{
scanf("%d",&T);
for (int k=1;
k<=T;
k++)
{
scanf("%d",&n);
build(1,n,1);
scanf("%d",&m);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
update(a,b,c,1,n,1);
}
printf("Case %d: The total value of the hook is %d.\n",k,sum[1]);
} return 0;
} 【中级数据结构-线段树|【hdu1698】just a hook】
