DDOSvoid's Blog

Luogu P4314 CPU监控

发表于 分类于
本文字数： 3.3k 阅读时长 ≈ 3 分钟

题目描述

https://www.luogu.com.cn/problem/P4314

简要题意：给定一个长度为 $n$ 的序列，现在有 $m$ 次操作，操作分别是区间加，区间赋值，求区间最大值，求区间历史最大值

$n,m \le 10^5$

Solution

注意到在进行一次区间赋值后，区间加也相当于区间赋值，另外对于历史最大值，我们只需要记录区间加标记的最大前缀和区间赋值的最大值即可

对于标记的维护，我们仍然沿用不同值标记分开维护的思路，所以我们需要维护：区间和、区间最大值、区间历史最大值、区间加标记、区间赋值标记、历史最大值区间加标记、历史最大值区间赋值标记

时间复杂度 $O(n\log n)$

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
#include <iostream>
#include <algorithm>
#define maxn 100010
#define INF 1000000000
using namespace std;

int n, m, a[maxn];

#define lc i << 1
#define rc i << 1 | 1 
struct Seg {
    int mx, tmx, add, tadd, cov, tcov;
    // mx 区间最大值 add 区间加标记 cov 区间赋值标记
    // tmx 区间历史最大值 tadd 历史最大值区间加标记 tcov 历史最大值区间赋值标记
} T[maxn * 4];
inline void maintain(int i) {
    T[i].mx = max(T[lc].mx, T[rc].mx);
    T[i].tmx = max(T[lc].tmx, T[rc].tmx);
}

void build(int i, int l, int r) {
    T[i].cov = T[i].tcov = -INF;
    if (l == r) return T[i] = { a[l], a[l] }, void();
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i);
}

inline void Update(int i, int add, int tadd, int cov, int tcov) {
    T[i].tmx = max({ T[i].tmx, T[i].mx + tadd, tcov });
    T[i].mx = cov == -INF ? T[i].mx + add : cov;
    if (T[i].cov == -INF) {
        T[i].tadd = max(T[i].tadd, T[i].add + tadd), T[i].add += add;
        T[i].tcov = tcov; T[i].cov = cov;
    }
    else {
        T[i].tcov = max({ T[i].tcov, T[i].cov + tadd, tcov });
        T[i].cov = cov == -INF ? T[i].cov + add : cov;
    }
}

inline void pushdown(int i) {
    int &add = T[i].add, &tadd = T[i].tadd, &cov = T[i].cov, &tcov = T[i].tcov;
    Update(lc, add, tadd, cov, tcov); Update(rc, add, tadd, cov, tcov);
    add = tadd = 0; cov = tcov = -INF;
}

void update_v(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update(i, v, v, -INF, -INF);
    int m = l + r >> 1; pushdown(i);
    update_v(lc, l, m, L, R, v); update_v(rc, m + 1, r, L, R, v);
    maintain(i); 
}

void update_cov(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update(i, 0, 0, v, v);
    int m = l + r >> 1; pushdown(i); 
    update_cov(lc, l, m, L, R, v); update_cov(rc, m + 1, r, L, R, v);
    maintain(i); 
}

int query_mx(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return -INF;
    if (L <= l && r <= R) return T[i].mx;
    int m = l + r >> 1; pushdown(i);
    return max(query_mx(lc, l, m, L, R), query_mx(rc, m + 1, r, L, R));
}

int query_tmx(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return -INF;
    if (L <= l && r <= R) return T[i].tmx;
    int m = l + r >> 1; pushdown(i);
    return max(query_tmx(lc, l, m, L, R), query_tmx(rc, m + 1, r, L, R));
}

inline void solve_1() {
    int x, y; cin >> x >> y;
    cout << query_mx(1, 1, n, x, y) << "\n";
}

inline void solve_2() {
    int x, y; cin >> x >> y;
    cout << query_tmx(1, 1, n, x, y) << "\n";
}

inline void solve_3() {
    int x, y, z; cin >> x >> y >> z;
    update_v(1, 1, n, x, y, z); 
}

inline void solve_4() {
    int x, y, z; cin >> x >> y >> z;
    update_cov(1, 1, n, x, y, z); 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> m; build(1, 1, n); 
    for (int i = 1; i <= m; ++i) {
        char c[10]; cin >> c;
        switch (c[0]) {
        case 'Q' : solve_1(); break;
        case 'A' : solve_2(); break;
        case 'P' : solve_3(); break;
        case 'C' : solve_4(); break; 
        }
    }
    return 0;
}