[USACO15DEC] Counting Haybale P

题意

给定一个长度为 N 的数组，表示每块地里的干草堆数量。

接下来有三种操作：

P l r c：把区间 [l, r] 每个位置都加上 c
M l r：查询区间 [l, r] 的最小值
S l r：查询区间 [l, r] 的元素和

对于每个查询输出答案。

思路

先看一个最直接的小数据写法：

cpp

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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：直接维护原数组。
// 区间加时逐个修改，查询最小值和区间和时逐个扫描。

const int MAXN = 200000 + 5;

int n, q;
long long a[MAXN];

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

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    while (q--) {
        char op;
        cin >> op;
        if (op == 'P') {
            int l, r;
            long long c;
            cin >> l >> r >> c;
            for (int i = l; i <= r; i++) {
                a[i] += c;
            }
        } else if (op == 'M') {
            int l, r;
            cin >> l >> r;
            long long ans = (1LL << 60);
            for (int i = l; i <= r; i++) {
                ans = min(ans, a[i]);
            }
            cout << ans << '\n';
        } else {
            int l, r;
            cin >> l >> r;
            long long ans = 0;
            for (int i = l; i <= r; i++) {
                ans += a[i];
            }
            cout << ans << '\n';
        }
    }

    return 0;
}

brute.cpp 直接维护原数组：

区间加时逐个修改
查最小值时逐个扫描
查区间和时逐个累加

这个做法容易懂，但一次区间操作最坏就要处理整段，肯定不够快。

优化时，用一棵懒标记线段树同时维护两类信息：

区间和
区间最小值

关键观察是：如果一个节点表示区间 [l, r]，整段都加上 c 时：

区间和增加 (r-l+1) * c
区间最小值增加 c

这说明整段加法对这两个量都能直接更新，不需要立刻递归到底。

于是在线段树节点上维护：

seg_sum[u]
seg_min[u]

再维护一个懒标记：

lazy_add[u]

表示这段区间还有多少“整体加法”没有下传给儿子。

这样：

区间加：整段命中时直接更新当前节点和懒标记
查最小值 / 区间和：必要时先下传懒标记，再递归查询

就能把三种操作都压到 $O(log N)$ 。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200000 + 5;

int n, q;
long long a[MAXN];
long long seg_sum[MAXN << 2];
long long seg_min[MAXN << 2];
long long lazy_add[MAXN << 2];

void push_up(int u) {
    seg_sum[u] = seg_sum[u << 1] + seg_sum[u << 1 | 1];
    seg_min[u] = min(seg_min[u << 1], seg_min[u << 1 | 1]);
}

void apply_add(int u, int l, int r, long long val) {
    seg_sum[u] += (r - l + 1) * val;
    seg_min[u] += val;
    lazy_add[u] += val;
}

void push_down(int u, int l, int r) {
    if (lazy_add[u] == 0 || l == r) {
        return;
    }

    int mid = (l + r) >> 1;
    apply_add(u << 1, l, mid, lazy_add[u]);
    apply_add(u << 1 | 1, mid + 1, r, lazy_add[u]);
    lazy_add[u] = 0;
}

void build(int u, int l, int r) {
    if (l == r) {
        seg_sum[u] = a[l];
        seg_min[u] = a[l];
        return;
    }

    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    push_up(u);
}

void update(int u, int l, int r, int ql, int qr, long long val) {
    if (ql <= l && r <= qr) {
        apply_add(u, l, r, val);
        return;
    }

    push_down(u, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) {
        update(u << 1, l, mid, ql, qr, val);
    }
    if (qr > mid) {
        update(u << 1 | 1, mid + 1, r, ql, qr, val);
    }
    push_up(u);
}

long long query_sum(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return seg_sum[u];
    }

    push_down(u, l, r);
    int mid = (l + r) >> 1;
    long long ans = 0;
    if (ql <= mid) {
        ans += query_sum(u << 1, l, mid, ql, qr);
    }
    if (qr > mid) {
        ans += query_sum(u << 1 | 1, mid + 1, r, ql, qr);
    }
    return ans;
}

long long query_min(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return seg_min[u];
    }

    push_down(u, l, r);
    int mid = (l + r) >> 1;
    long long ans = (1LL << 60);
    if (ql <= mid) {
        ans = min(ans, query_min(u << 1, l, mid, ql, qr));
    }
    if (qr > mid) {
        ans = min(ans, query_min(u << 1 | 1, mid + 1, r, ql, qr));
    }
    return ans;
}

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

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    build(1, 1, n);

    while (q--) {
        char op;
        cin >> op;
        if (op == 'P') {
            int l, r;
            long long c;
            cin >> l >> r >> c;
            update(1, 1, n, l, r, c);
        } else if (op == 'M') {
            int l, r;
            cin >> l >> r;
            cout << query_min(1, 1, n, l, r) << '\n';
        } else {
            int l, r;
            cin >> l >> r;
            cout << query_sum(1, 1, n, l, r) << '\n';
        }
    }

    return 0;
}

复杂度

建树复杂度：

$O(N)$

每次操作复杂度：

$O(log N)$

总时间复杂度：

$O(N + Q log N)$

空间复杂度：

$O(N)$

总结

这题最核心的点不是线段树本身，而是看出：

区间加对 sum 和 min 的影响都可以整段计算

一旦抓住这一点，就只是在一棵懒标记线段树上同时挂两种维护量。

[USACO15DEC] Counting Haybale P

目录

题意

思路

代码

复杂度

总结