HDU 1698.Just a Hook-线段树(成段替换、输出总和tree[1])

HDU1698.Just a Hook

这个题是最最基础的成段更新的线段数的题目，直接贴代码吧。

代码:

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<cstdlib>

 #include<queue>

 #include<stack>

 #include<map>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 const int inf=0x3f3f3f3f;

 const double eps=1e-;

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 int tree[maxn<<],add[maxn<<];

 void pushup(int rt)

 {

     tree[rt]=tree[rt<<]+tree[rt<<|];

 }

 void pushdown(int rt,int m)

 {

     if(add[rt]){

         add[rt<<]=add[rt<<|]=add[rt];

         tree[rt<<]=(m-(m>>))*add[rt];

         tree[rt<<|]=(m>>)*add[rt];

         add[rt]=;

     }

 }

 void build(int l,int r,int rt)

 {

     add[rt]=;

     tree[rt]=;

     if(l==r){

         return ;

     }

     int m=(l+r)>>;

     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){

         add[rt]=c;

         tree[rt]=c*(r-l+);

         return ;

     }

     pushdown(rt,r-l+);

     int m=(l+r)>>;

     if(L<=m) update(L,R,c,lson);

     if(R> m) update(L,R,c,rson);

     pushup(rt);

 }

 int main()

 {

     int t,n,m;

     while(~scanf("%d",&t)){

         int cas=;

         while(t--){

             cas++;

             scanf("%d%d",&n,&m);

             build(,n,);

             for(int i=;i<=m;i++){

                 int l,r,c;

                 scanf("%d%d%d",&l,&r,&c);

                 update(l,r,c,,n,);

             }

             printf("Case %d: The total value of the hook is %d.\n",cas,tree[]);

         }

     }

     return ;

 }