首页 > 代码库 > HDU 1698 Just a Hook (线段树区间更新)
HDU 1698 Just a Hook (线段树区间更新)
题目链接
题意 : 一个有n段长的金属棍,开始都涂上铜,分段涂成别的,金的值是3,银的值是2,铜的值是1,然后问你最后这n段总共的值是多少。
思路 : 线段树的区间更新。可以理解为线段树成段更新的模板题。
1 //HDU 1698 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 6 using namespace std; 7 8 int lz[500010],p[500010] ; 9 10 //lz延迟标记,每次更新不需要更新到底,使得更新延迟到下次更新或者查询的时候11 void pushdown(int rt,int m)12 {13 if(lz[rt])14 {15 lz[rt << 1] = lz[rt] ;16 lz[rt << 1 | 1] = lz[rt] ;17 p[rt << 1] = (m -( m >> 1)) * lz[rt] ;18 p[rt << 1 | 1] = (m>>1) * lz[rt] ;19 lz[rt] = 0 ;20 }21 }22 void pushup(int rt) // 将左右孩子的值更新到自己23 {24 p[rt] = p[rt << 1] + p[rt << 1 | 1] ;25 }26 27 void update(int L,int R,int l,int r,int sc,int rt)28 {29 if(l >= L && r <= R)30 {31 32 lz[rt] = sc ;33 p[rt] = (r-l+1)*sc ;34 return ;35 }36 pushdown(rt,r-l+1) ;37 int m = (r + l ) >> 1 ;38 if(m >= L)39 update(L,R,l,m,sc,rt << 1) ;40 if(R > m)41 update(L,R,m+1,r,sc,rt << 1 | 1) ;42 pushup(rt) ;43 }44 void build(int l,int r,int rt)45 {46 lz[rt] = 0 ;47 if(l == r)48 {49 p[rt] = 1 ;50 return ;51 }52 int mid = (l + r) >> 1 ;53 build(l,mid,rt << 1) ;54 build(mid + 1,r,rt << 1 | 1) ;55 pushup(rt) ;56 }57 int query(int L,int R,int l,int r,int rt)58 {59 int sum = 0 ;60 if(L <= l && r <= R)61 {62 63 return p[rt] ;64 }65 pushdown(rt , r-l+1) ;66 int mid = (l + r) >> 1 ;67 if(mid >= L)68 sum += query(L,R,l,mid,rt << 1 ) ;69 if(mid < R)70 sum += query(L,R,mid+1,r,rt << 1 | 1) ;71 return sum ;72 73 }74 int main()75 {76 int T,N,Q ;77 cin >> T ;78 int casee = 1 ;79 while(T--)80 {81 int x,y,z ;82 cin >> N >> Q ;83 build(1,N,1) ;84 while(Q--)85 {86 cin >> x >> y >> z ;87 update(x,y,1,N,z,1) ;88 }89 int sum = query(1,N,1,N,1) ;90 cout<<"Case "<< casee ++ <<": The total value of the hook is "<<sum <<"."<<endl ;91 }92 return 0 ;93 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。