HDU 1166 Just a Hook

Description

区间更新，区间查询（注意val初始值非0）

题目链接

Code

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 100005;

struct node
{
    int L, R, val, lazy;
} a[N << 2 | 1];

void down(int x)
{
    if(a[x].lazy > 0)
    {
        a[x << 1].val = a[x].lazy * (a[x << 1].R - a[x << 1].L + 1);
        a[x << 1].lazy = a[x].lazy;
        a[x << 1 | 1].val = a[x].lazy * (a[x << 1 | 1].R - a[x << 1 | 1].L + 1);
        a[x << 1 | 1].lazy = a[x].lazy;
        a[x].lazy = 0;
    }
}

void init(int num, int l, int r)
{
    a[num].L = l;
    a[num].R = r;
    a[num].val = 1;
    a[num].lazy = 0;

    if(l == r)
        return ;
    int mid = (l + r) >> 1;
    init(num << 1, l, mid);
    init(num << 1 | 1, mid + 1, r);
    ///val != 0
    a[num].val = a[num << 1].val + a[num << 1 | 1].val;
}

void update(int num, int l, int r, int tot)
{
    if(a[num].L == l && a[num].R == r)
    {
        a[num].val = tot * (r - l + 1);
        a[num].lazy = tot;
        return ;
    }
    if(a[num].L == a[num].R)
        return ;
    down(num);
    int mid = (a[num].L + a[num].R) >> 1;
    if(mid >= r)
        update(num << 1, l, r, tot);
    else if(mid < l)
        update(num << 1 | 1, l, r, tot);
    else
    {
        update(num << 1, l, mid, tot);
        update(num << 1 | 1, mid + 1, r, tot);
    }
    a[num].val = a[num << 1].val + a[num << 1 | 1].val;
}

//void update(int num, int l, int r, int tot)
//{
//    if(a[num].L > r || a[num].R < l)
//        return ;
//    if(a[num].L >= l && a[num].R <= r)
//    {
//        a[num].val = tot * (a[num].R - a[num].L + 1);
//        a[num].lazy = tot;
//        return ;
//    }
//    down(num);
//    update(num << 1, l, r, tot);
//    update(num << 1 | 1, l, r, tot);
//    a[num].val = a[num << 1].val + a[num << 1 | 1].val;
//}

///int query(int num, int l, int r)如果需要勿忘down(num)


int main()
{
    int t;
    while(~scanf("%d", &t))
    {
        int tem = t;
        int n, m, b, c, d;
        while(t--)
        {
            scanf("%d%d", &n, &m);
            init(1, 1, n);
            while(m--)
            {
                scanf("%d%d%d", &b, &c, &d);
                update(1, b, c, d);
            }
            printf("Case %d: The total value of the hook is %d.\n", tem - t, a[1].val);
        }
    }
    return 0;
}
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103