洛谷 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);
    }
}