題目：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(成段更新)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。