生活随笔
收集整理的這篇文章主要介紹了
hdu 1698(线段树区间更新)
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
解題思路：線段樹區(qū)間更新水題。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;const int maxn = 100005;
struct seg
{int l,r,sum,lazy;
}tree[maxn<<2];void build(int l,int r,int u)
{tree[u].l = l;tree[u].r = r;tree[u].lazy = 0;tree[u].sum = 0;if(l == r) return;int mid = (l + r) >> 1;build(l,mid,2*u);build(mid+1,r,2*u+1);
}void PushDown(int u)
{tree[2*u].sum = (tree[2*u].r - tree[2*u].l + 1) * tree[u].lazy;tree[2*u+1].sum = (tree[2*u+1].r - tree[2*u+1].l + 1) * tree[u].lazy;tree[2*u].lazy = tree[u].lazy;tree[2*u+1].lazy = tree[u].lazy;tree[u].lazy = 0;
}void PushUp(int u)
{tree[u].sum = tree[2*u].sum + tree[2*u+1].sum;
}void update(int l,int r,int u,int v)
{if(tree[u].l >= l && tree[u].r <= r){tree[u].sum = (tree[u].r - tree[u].l + 1) * v;tree[u].lazy = v;return;}if(tree[u].lazy) PushDown(u);int mid = (tree[u].l + tree[u].r) >> 1;if(l <= mid) update(l,r,u*2,v);if(r > mid) update(l,r,u*2+1,v);PushUp(u);
}int query(int l,int r,int u)
{if(tree[u].l >= l && tree[u].r <= r){return tree[u].sum;}int mid = (tree[u].l + tree[u].r) >> 1;int ans = 0;if(l <= mid) ans += query(l,r,2*u);if(r > mid) ans += query(l,r,2*u+1);return ans;
}int main()
{int t,cas = 1;scanf("%d",&t);while(t--){int n;scanf("%d",&n);build(1,n,1);for(int i = 1; i <= n; i++)update(i,i,1,1);int q,x,y,z;scanf("%d",&q);while(q--){scanf("%d%d%d",&x,&y,&z);update(x,y,1,z);}printf("Case %d: The total value of the hook is %d.\n",cas++,query(1,n,1));}return 0;
}
總結
以上是生活随笔為你收集整理的hdu 1698(线段树区间更新)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
