洛谷P4314 CPU【线段树】

题意

Bob 需要一个程序来监视 CPU 使用率。这是一个很繁琐的过程，为了让问题更加简单，Bob 会慢慢列出今天会在用计算机时做什么事。

Bob 会干很多事，除了跑暴力程序看视频之外，还会做出去玩玩和用鼠标乱点之类的事，甚至会一脚踢掉电源……这些事有的会让做这件事的这段时间内 CPU 使用率增加或减少一个值；有的事还会直接让 CPU 使用率变为一个值。

当然 Bob 会询问：在之前给出的事件影响下，CPU 在某段时间内，使用率最高是多少。有时候 Bob 还会好奇地询问，在某段时间内 CPU 曾经的最高使用率是多少。

为了使计算精确，使用率不用百分比而用一个整数表示。

不保证 Bob 的事件列表出了莫名的问题，使得使用率为负………………

思路

需要支持的区间操作有：

• 区间加法
• 区间设置
• 区间查询最大值
• 区间查询历史最大值

对于查询最大值的操作，是比较经典的操作，维护一个区间最大值$mx$，并用两个懒标记$addlz$和$setlz$辅助。
对于查询历史最大值的操作，也是维护一个区间历史最大值$mx\_his$，并用两个懒标记$his\_add$和$his\_set$辅助。
区间合并操作十分简单，两个子区间取一下最大值即可。下传懒标记比较麻烦，下面进行分析。
首先，懒标记的本质其实是，当前区间的若干操作序列的合并（加法标记是若干次加法操作的合并，设置标记是若干次设置操作的合并），可以发现，如果某个区间出现一次设置操作，之后的所有加法操作就可以等效地看成设置操作。
所以，每个区间的操作序列只有两种情况：

• 全都是加法操作
• 先加法操作再设置操作（若没有加法操作也不影响）

首先考虑加法标记的下传，若子区间没有设置操作（设置标记为空），那么进行加法标记的下传；否则把加法标记转化为设置标记的下传。加法标记下传实现如下：

void push_Add(int i, int add, int his_add) // i: 子区间对应的节点 add: 父亲节点的加法标记 his_add: 父亲节点的历史最大加法标记累加
{
	// 历史最大值 有两种可能，一种是原序列的历史最大值，一种是原序列最大值加上新的操作序列之后的最大值
    t[i].mx_his = max(t[i].mx + his_add, t[i].mx_his);
    // 与历史最大值类似     
    t[i].add_his = max(t[i].addlz + his_add, t[i].add_his);
    // 最大值和加法标记直接更新即可
    t[i].mx += add;
    t[i].addlz += add; 
}
1
2
3
4
5
6
7
8
9
10

对于设置标记的下传，若父区间存在设置标记，则直接下传即可。实现如下：

void push_Set(int i, int set, int his_set) // i: 子区间对应的节点 set: 父亲节点的设置标记 his_set: 父亲节点的历史最大设置标记
{
    if (t[i].has_set) // 如果子节点存在设置标记，要与父节点的设置标记比较一下，其他的下传都比较简单
    {
        t[i].mx = set;
        t[i].setlz = set;
        t[i].mx_his = max(his_set, t[i].mx_his);
        t[i].set_his = max(t[i].set_his, his_set); 
    }
    else 
    {
        t[i].has_set = true;
        t[i].mx = set;
        t[i].setlz = set;
        t[i].mx_his = max(his_set, t[i].mx_his);
        t[i].set_his = his_set;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 100005;

int a[N];

struct TreeNode
{
    int l, r;
    int mx, mx_his;
    int addlz, setlz;
    int add_his, set_his;
    bool has_set;
}t[N << 2];

void push_up(int i)
{
    t[i].mx = max(t[i << 1].mx, t[i << 1 | 1].mx);
    t[i].mx_his = max(t[i << 1].mx_his, t[i << 1 | 1].mx_his);
}

void push_Add(int i, int add, int his_add)
{
    t[i].mx_his = max(t[i].mx + his_add, t[i].mx_his);
    t[i].add_his = max(t[i].addlz + his_add, t[i].add_his);
    t[i].mx += add;
    t[i].addlz += add; 
}

void push_Set(int i, int set, int his_set)
{
    if (t[i].has_set)
    {
        t[i].mx = set;
        t[i].setlz = set;
        t[i].mx_his = max(his_set, t[i].mx_his);
        t[i].set_his = max(t[i].set_his, his_set);
    }
    else 
    {
        t[i].has_set = true;
        t[i].mx = set;
        t[i].setlz = set;
        t[i].mx_his = max(his_set, t[i].mx_his);
        t[i].set_his = his_set;
    }
}

void push_down(int i)
{
    if (t[i << 1].has_set)
        push_Set(i << 1, t[i << 1].setlz + t[i].addlz, t[i << 1].setlz + t[i].add_his);
    else 
        push_Add(i << 1, t[i].addlz, t[i].add_his);
    if (t[i << 1 | 1].has_set)
        push_Set(i << 1 | 1, t[i << 1 | 1].setlz + t[i].addlz, t[i << 1 | 1].setlz + t[i].add_his);
    else 
        push_Add(i << 1 | 1, t[i].addlz, t[i].add_his);
    if (t[i].has_set)
    {
        push_Set(i << 1, t[i].setlz, t[i].set_his);
        push_Set(i << 1 | 1, t[i].setlz, t[i].set_his);
    }

    t[i].has_set = false;
    t[i].addlz = t[i].add_his = t[i].setlz = t[i].set_his = 0;
}

void build(int i, int l, int r)
{
    t[i].l = l, t[i].r = r;
    if (l == r)
    {
        t[i].mx = t[i].mx_his = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    push_up(i);
}

void updateAdd(int i, int l, int r, int k)
{
    if (l <= t[i].l && t[i].r <= r) 
    {
        if (t[i].has_set)
            push_Set(i, t[i].setlz + k, t[i].setlz + k);
        else 
            push_Add(i, k, k);
        return;
    }
    push_down(i);
    int mid = (t[i].l + t[i].r) >> 1;
    if (l <= mid) updateAdd(i << 1, l, r, k);
    if (r > mid) updateAdd(i << 1 | 1, l, r, k);
    push_up(i);
}

void updateSet(int i, int l, int r, int k)
{
    if (l <= t[i].l && t[i].r <= r)
    {
        push_Set(i, k, k);
        return;
    }
    push_down(i);
    int mid = (t[i].l + t[i].r) >> 1;
    if (l <= mid) updateSet(i << 1, l, r, k);
    if (r > mid) updateSet(i << 1 | 1, l, r, k);
    push_up(i);
}

int queryMx(int i, int l, int r)
{
    if (l <= t[i].l && t[i].r <= r) return t[i].mx;
    push_down(i);
    int s = -0x3f3f3f3f;
    int mid = (t[i].l + t[i].r ) >> 1;
    if (l <= mid) s = max(s, queryMx(i << 1, l, r));
    if (r > mid) s = max(s, queryMx(i << 1 | 1, l, r));
    return s;
}

int queryHisMx(int i, int l, int r)
{
    if (l <= t[i].l && t[i].r <= r) return t[i].mx_his;
    push_down(i);
    int s = -0x3f3f3f3f;
    int mid = (t[i].l + t[i].r) >> 1;
    if (l <= mid) s = max(s, queryHisMx(i << 1, l, r));
    if (r > mid) s = max(s, queryHisMx(i << 1 | 1, l, r));
    return s;
}

int main()
{
    #ifdef ZYCMH
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &a[i]);

    build(1, 1, n);

    int m;
    scanf("%d", &m);
    for (int i = 1; i <= m; i ++ )
    {
        char op;
        int l, r, x;
        scanf("\n%c", &op);
        scanf("%d%d", &l, &r);
        if (op == 'A') printf("%d\n", queryHisMx(1, l, r));
        else if(op == 'Q') printf("%d\n", queryMx(1, l, r));
        else if(op == 'P')
        {
            scanf("%d", &x);
            updateAdd(1, l, r, x);
        }
        else if(op == 'C')
        {
            scanf("%d", &x);
            updateSet(1, l, r, x);
        }
    }
    return 0;
}

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185