本文共 1650 字，大约阅读时间需要 5 分钟。

题目的大意是：

一开始有n个钩子，然后他们的价值全是1。

然后有Q次操作，然后每次有三个数x,y,z；你可以改变从x到y的区间的钩子的值为z。

然后最后一个询问，要你输出n个钩子的总价值是多少。

这里我首次接触到了lazy思想，实际上就是给完全包含当前区间的那个区间标记一下，然后不继续往下面更新，直到下次继续遇到这个区间并且需要继续往下面更新才把当前的lazy标记往下去更新。并且也不要忘记pushup更新操作。

以前的代码写的不好，现在在重新贴上来一发。。

现在重新再做这题，发现1A了，十分简单，O(∩_∩)O哈哈~，加油！

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;#define maxn 111111struct node{	int l,r;	int sum,flag,add;}tree[maxn*4];void pushup(int v){	int temp=v<<1;	tree[v].sum=tree[temp].sum+tree[temp+1].sum;}void pushdown(int v){	int temp=v<<1;	tree[temp].flag=tree[temp+1].flag=1;	tree[temp].sum=tree[v].add*(tree[temp].r-tree[temp].l+1);	tree[temp+1].sum=tree[v].add*(tree[temp+1].r-tree[temp+1].l+1);	tree[temp].add=tree[temp+1].add=tree[v].add;	tree[v].add=0;	tree[v].flag=0;}void build(int l,int r,int v){	tree[v].l=l;	tree[v].r=r;	tree[v].sum=1;	tree[v].flag=0;	tree[v].add=0;	if(l==r) return;	int mid=(tree[v].l+tree[v].r)>>1;	int temp=v<<1;	build(l,mid,temp);	build(mid+1,r,temp+1);	pushup(v);}void update(int l,int r,int v,int x){	if(tree[v].l==l&&tree[v].r==r){		tree[v].sum=x*(tree[v].r-tree[v].l+1);		tree[v].flag=1;		tree[v].add=x;		return;	}	if(tree[v].flag) pushdown(v);	int mid=(tree[v].l+tree[v].r)>>1;	int temp=v<<1;	if(r<=mid) update(l,r,temp,x);	else if(l>mid) update(l,r,temp+1,x);	else{		update(l,mid,temp,x);		update(mid+1,r,temp+1,x);	}	pushup(v);}int main(){	int T,n,Q;	while(~scanf("%d",&T)){		int jj=1;		while(T--){			scanf("%d%d",&n,&Q);			build(1,n,1);			while(Q--){				int x,y,z;				scanf("%d%d%d",&x,&y,&z);				update(x,y,1,z);			}			printf("Case %d: The total value of the hook is %d.\n",jj++,tree[1].sum);		}	}}
      
     
    
   

转载地址：https://blog.csdn.net/ACMer_hades/article/details/46489391 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！