洛谷 4314.CPU 监控

首先考虑若没有 \(\texttt C\) 操作该如何做。
可以在线段树上维护区间加标记和区间加标记的历史最大值,并以此在下推时更新儿子的最大值和历史最大值。

考虑 \(\texttt C\) 操作,若打区间加标记时存在区间覆盖标记,则可以将区间加操作仍然看做区间覆盖操作。
这样就分为两种情况,分别讨论维护即可。

参考了洛谷 @little_sun 的代码。

代码:

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
#include <cstdio>
#include <algorithm>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
const int N = 1e5;
const int inf = 1 << 31;
int n,m,a[N + 5];
struct node
{
int add,set,max;
int Add,Set,Max;
} seg[(N << 2) + 10];
void build(int p,int tl,int tr)
{
seg[p].set = seg[p].Set = inf;
if(tl == tr)
{
seg[p].max = seg[p].Max = a[tl];
return ;
}
int mid = tl + tr >> 1;
build(ls,tl,mid),build(rs,mid + 1,tr);
seg[p].max = max(seg[ls].max,seg[rs].max),
seg[p].Max = max(seg[ls].Max,seg[rs].Max);
}
inline void push_add(int p,int add,int Add)
{
if(seg[p].set > inf)
seg[p].Set = max(seg[p].Set,seg[p].set + Add),
seg[p].Max = max(seg[p].Max,seg[p].max + Add),
seg[p].set += add,seg[p].max += add;
else
seg[p].Add = max(seg[p].Add,seg[p].add + Add),
seg[p].Max = max(seg[p].Max,seg[p].max + Add),
seg[p].add += add,seg[p].max += add;
}
inline void push_set(int p,int set,int Set)
{
seg[p].Set = max(seg[p].Set,Set),
seg[p].Max = max(seg[p].Max,Set),
seg[p].set = seg[p].max = set;
}
inline void push(int p)
{
push_add(ls,seg[p].add,seg[p].Add),
push_add(rs,seg[p].add,seg[p].Add),
seg[p].add = seg[p].Add = 0;
if(seg[p].set > inf)
push_set(ls,seg[p].set,seg[p].Set),
push_set(rs,seg[p].set,seg[p].Set),
seg[p].set = seg[p].Set = inf;
}
void update_add(int l,int r,int k,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
{
push_add(p,k,k);
return ;
}
push(p);
int mid = tl + tr >> 1;
l <= mid && (update_add(l,r,k,ls,tl,mid),1);
r > mid && (update_add(l,r,k,rs,mid + 1,tr),1);
seg[p].max = max(seg[ls].max,seg[rs].max),
seg[p].Max = max(seg[ls].Max,seg[rs].Max);
}
void update_set(int l,int r,int k,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
{
push_set(p,k,k);
return ;
}
push(p);
int mid = tl + tr >> 1;
l <= mid && (update_set(l,r,k,ls,tl,mid),1);
r > mid && (update_set(l,r,k,rs,mid + 1,tr),1);
seg[p].max = max(seg[ls].max,seg[rs].max),
seg[p].Max = max(seg[ls].Max,seg[rs].Max);
}
int query_max(int l,int r,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
return seg[p].max;
push(p);
int mid = tl + tr >> 1;
int ret = inf;
l <= mid && (ret = max(ret,query_max(l,r,ls,tl,mid)));
r > mid && (ret = max(ret,query_max(l,r,rs,mid + 1,tr)));
return ret;
}
int query_Max(int l,int r,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
return seg[p].Max;
push(p);
int mid = tl + tr >> 1;
int ret = inf;
l <= mid && (ret = max(ret,query_Max(l,r,ls,tl,mid)));
r > mid && (ret = max(ret,query_Max(l,r,rs,mid + 1,tr)));
return ret;
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
build(1,1,n);
scanf("%d",&m);
char op;
int l,r,k;
for(;m;--m)
{
scanf(" %c%d%d",&op,&l,&r);
if(op == 'Q')
printf("%d\n",query_max(l,r,1,1,n));
else if(op == 'A')
printf("%d\n",query_Max(l,r,1,1,n));
else if(op == 'P')
scanf("%d",&k),update_add(l,r,k,1,1,n);
else
scanf("%d",&k),update_set(l,r,k,1,1,n);
}
}