线段树HDU1698(成段更新)

题目：Just a Hook

 

延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新or询问到的时候。

#include <stdio.h> #define N 111111#define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1int n;int col[N<<2]; int sum[N<<2];void PushUP(int rt) {sum[rt]=sum[rt<<1]+sum[rt<<1|1]; }void PushDown(int rt,int m) {if(col[rt]){col[rt<<1]=col[rt<<1|1]=col[rt];sum[rt<<1]=(m-(m>>1))*col[rt];sum[rt<<1|1]=(m>>1)*col[rt];col[rt]=0;} }void Build(int l,int r,int rt) {col[rt]=0;sum[rt]=1;if(l==r)return;int m=(l+r)>>1;Build(lson);Build(rson);PushUP(rt); }void Update(int L,int R,int c,int l,int r,int rt) {if(L<=l&&R>=r){col[rt]=c;sum[rt]=c*(r-l+1);return;}PushDown(rt,r-l+1);int m=(l+r)>>1;if(L<=m)Update(L,R,c,lson);if(R>m)Update(L,R,c,rson);PushUP(rt); }int main() {int t,m,n,k=1;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);Build(1,n,1);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(成段更新)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。