HDU 1698 Just a Hook（线段树）

题目大意

有 n(1<=n<=10^5) 个连续的 stick，编号从 1 到 n。每根 stick 有一个权值，起初的时候全是 1

有 m(1<=m<=10^5) 个操作，每次操作格式如下：

L R val：把第 L 个到第 R 个，每根 stick 的权值变为 val

做法分析

使用线段树标记一个区间中，所有 stick 的权值的和是多少

更新的时候使用“懒操作”

参考代码

HDU 1698

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 const int N=100006;
 8 int t, n, q, x, y, z;
 9 
10 struct interval_tree
11 {
12     struct data
13     {
14         int st, en, val, bj;
15         data() {}
16         data(int a, int b, int c, int d)
17         {
18             st=a, en=b, val=c, bj=d;
19         }
20     } T[N<<2];
21 
22     void build(int id, int L, int R)
23     {
24         T[id]=data(L, R, R-L+1, 0);
25         if(L==R) return;
26         int mid=(L+R)>>1;
27         build(id<<1, L, mid);
28         build(id<<1|1, mid+1, R);
29     }
30 
31     void push_down(int id)
32     {
33         if(T[id].bj==0) return;
34         T[id<<1].bj=T[id<<1|1].bj=T[id].bj;
35         T[id<<1].val=(T[id<<1].en-T[id<<1].st+1)*T[id].bj;
36         T[id<<1|1].val=(T[id<<1|1].en-T[id<<1|1].st+1)*T[id].bj;
37         T[id].bj=0;
38     }
39 
40     void update(int id, int L, int R, int val)
41     {
42         if(L<=T[id].st && T[id].en<=R)
43         {
44             T[id].val=val*(T[id].en-T[id].st+1);
45             T[id].bj=val;
46             return;
47         }
48         push_down(id);
49         int mid=(T[id].st+T[id].en)>>1;
50         if(R<=mid) update(id<<1, L, R, val);
51         else if(L>mid) update(id<<1|1, L, R, val);
52         else update(id<<1, L, R, val), update(id<<1|1, L, R, val);
53         T[id].val=T[id<<1].val+T[id<<1|1].val;
54     }
55 } tree;
56 
57 int main()
58 {
59     scanf("%d", &t);
60     for(int ca=1; ca<=t; ca++)
61     {
62         scanf("%d%d", &n, &q);
63         tree.build(1, 1, n);
64         while(q--)
65         {
66             scanf("%d%d%d", &x, &y, &z);
67             tree.update(1, x, y, z);
68         }
69         printf("Case %d: The total value of the hook is %d.\n", ca, tree.T[1].val);
70     }
71     return 0;
72 }

AC通道

HDU 1698 Just a Hook