hdu 1698 线段树成段更新

题意：一段钩子，每个钩子的值为1，有若干更新，每次跟新某段的值，若干查询某段的和

基础题了

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define MOD 1000000007
10 const int INF=0x3f3f3f3f;
11 const double eps=1e-5;
12 #define cl(a) memset(a,0,sizeof(a))
13 #define ts printf("*****
");
14 #define lson l,mid,rt<<1
15 #define rson mid+1,r,rt<<1|1
16 #define root 1,n,1
17 #define mid ((l+r)>>1)
18 const int MAXN=111111;
19 int n,m,t,Min;
20 int sum[MAXN<<2],col[MAXN<<2];
21 void pushup(int rt){
22     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
23 }
24 void pushdown(int rt,int m)
25 {
26     if(col[rt]!=0)
27     {
28         sum[rt<<1]=(m-(m>>1))*col[rt];  //位运算一定要带括号
29         sum[rt<<1|1]=(m>>1)*col[rt];
30         col[rt<<1]=col[rt<<1|1]=col[rt];
31         col[rt]=0;
32     }
33 }
34 void build(int l,int r,int rt){
35     col[rt]=0;
36     sum[rt]=1;
37     if(l==r)    return;
38     build(lson);
39     build(rson);
40     pushup(rt);
41 }
42 void update(int L,int R,int val,int l,int r,int rt)
43 {
44     if(l>=L&&r<=R)
45     {
46         col[rt]=val;
47         sum[rt]=(r-l+1)*val;
48         return;
49     }
50     if(L>r||R<l)
51         return ;
52     pushdown(rt,r-l+1);
53     update(L,R,val,lson);
54     update(L,R,val,rson);
55     pushup(rt);
56 }
57 int main()
58 {
59     int i,j,k;
60     #ifndef ONLINE_JUDGE
61     freopen("1.in","r",stdin);
62     #endif
63     int l,t,o,a,b,c,tt;
64     scanf("%d",&tt);
65     for(int cas=1;cas<=tt;cas++)
66     {
67         scanf("%d%d",&n,&m);
68         build(root);
69         while(m--)
70         {
71             int a,b,c;
72             scanf("%d%d%d",&a,&b,&c);
73             update(a,b,c,root);
74         }
75         printf("Case %d: The total value of the hook is %d.
",cas,sum[1]);
76     }
77 }

hdu 1698 线段树 成段更新

hdu 1698 线段树成段更新