首页 > 代码库 > HDU 1698 Just a Hook （线段树区间更新）

HDU 1698 Just a Hook （线段树区间更新）

2024-07-15 00:22:20   230人阅读

题目链接

题意 ： 一个有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 }
View Code

 


联系
我们