梦魔 - 题目列表

梦魔

GitHub跳转原题关系图 Canvas 关系图返回列表

用端点贪心把每个梦魔的限制转成嵌套区间，再用单调栈和计数排序在线性时间求出所有落点答案。

OJ: shumeng

题目 ID: CSP202412E

难度:提高+/省选-

标签:贪心单调栈前缀和区间最值

日期: 2026-07-31 16:21

形式化题目

$n$ 只梦魔排成一列，梦魔 $i$ 防御力为 $a_i$ ，击杀后攻击力增加 $b_i$ 。初始攻击力为 $x$ ，从间隙 $p$ （第 $p$ 与第 $p+1$ 只之间）开始，每次只能击杀当前最左端或最右端的梦魔，且当前攻击力必须不小于其防御力。

对每个 $p = 1 \dots n-1$ ，求能击杀全部梦魔所需的最小初始攻击力 $f(p)$ ，输出所有 $f(p)$ 的异或和。每次修改都从初始数组重新开始。

思路

朴素做法：递归选择端点

先看直接做法：固定落点后，每次递归选择击杀左端或右端，返回所需的最小初始攻击力。

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，把每次选择左端或右端看成递归分支，只适合小规模对拍。
#include <bits/stdc++.h>
using namespace std;

int n;
vector<long long> a;
vector<long long> b;

// 当前左右边界为 left、right（已击杀范围之外的第一个），返回所需的最小初始攻击力
long long dfs(int left, int right) {
    if (left == 0 && right == n + 1) return 0;

    long long answer = (1LL << 62);
    if (left > 0) {
        long long need_after = dfs(left - 1, right);
        long long need_now = max(a[left], need_after - b[left]);
        answer = min(answer, need_now);
    }
    if (right <= n) {
        long long need_after = dfs(left, right + 1);
        long long need_now = max(a[right], need_after - b[right]);
        answer = min(answer, need_now);
    }
    return answer;
}

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

    cin >> n;
    vector<long long> base_a(n + 2);
    vector<long long> base_b(n + 2);
    a.assign(n + 2, 0);
    b.assign(n + 2, 0);

    for (int i = 1; i <= n; i++) cin >> base_a[i];
    for (int i = 1; i <= n; i++) cin >> base_b[i];

    int q;
    cin >> q;
    for (int query = 0; query < q; query++) {
        a = base_a;
        b = base_b;

        int changed;
        cin >> changed;
        for (int i = 0; i < changed; i++) {
            int position;
            cin >> position >> a[position] >> b[position];
        }

        // 对每个间隙 p 独立递归求解，再取异或
        long long answer = 0;
        for (int split = 1; split < n; split++) {
            answer ^= dfs(split, split + 1);
        }
        cout << answer << '\n';
    }

    return 0;
}

每个间隙都要枚举两端的所有击杀顺序，只适合小数据验证。

固定落点的贪心

固定间隙 $p$ 后，左侧梦魔只能按 $p, p-1, \dots, 1$ 的顺序出现，右侧只能按 $p+1, p+2, \dots, n$ 的顺序出现，任意时刻只有左右两个端点可选。

若两端防御力满足 $x \le y$ ，优先击杀 $x$ 不会变差：设某方案先击杀右端 $y$ 后再击杀左端 $x$ ，把它改成先击杀 $x$ ，再按原顺序击杀右侧那些梦魔， $x$ 的防御力不超过第一个右端点且提前获得 $b_x$ ，每一步攻击力都不更低，方案依然可行。

于是贪心策略确定：始终优先击杀防御力较小的端点。问题变成在贪心过程中，每一步对初始攻击力提出什么下界。

一个梦魔产生两个区间限制

用单调栈求每个位置两侧“最近的不小于自己”的边界：

L[j] = j \text{ 左侧最近的 } a[L[j]] \ge a[j] \text{ 的位置，不存在时为 } 0;

R[j] = j \text{ 右侧最近的 } a[R[j]] \ge a[j] \text{ 的位置，不存在时为 } n+1。

求 $L$ 、 $R$ 时单调栈只能弹出严格更小的防御力，相等的必须保留。

若 $j$ 位于落点右侧（ $p < j$ ），当 $L[j] \le p \le j-1$ 时， $j$ 左侧直到 $L[j]$ 之间的梦魔防御力都严格小于 $a_j$ ，贪心会先击杀它们， $j$ 才成为关键端点，因此产生限制：

\text{落点区间 } [\max(1, L[j]),\ j-1], \qquad \text{限制值 } a_j - (\text{prefix}_b[j-1] - \text{prefix}_b[L[j]])。

若 $j$ 位于落点左侧（ $p \ge j$ ），对称地得到：

\text{落点区间 } [j,\ \min(n-1, R[j]-1)], \qquad \text{限制值 } a_j - (\text{prefix}_b[R[j]-1] - \text{prefix}_b[j])。

其中 $\text{prefix}_b[t]$ 是 $b_1 + \dots + b_t$ 。区间里每个 $p$ 都必须满足该限制，所以 $f(p)$ 是覆盖它的所有候选限制值的最大值。

嵌套区间扫描

这些候选区间不会交叉：任意两个区间要么相离、相等，要么一个包含另一个（否则交叉部分会同时违反“最近不小于自己”的定义）。把区间按 $(\text{left 升序}, \text{right 降序})$ 排序，扫描 $p = 1 \dots n-1$ 时，已经开始但尚未结束的区间正好形成一条嵌套链：

text

1
2
3外层区间 [1, 8]
    内层区间 [3, 6]
        更内层区间 [4, 5]

用栈维护这条链：进入新区间时，栈节点保存“从栈底到该节点的限制值最大值”；区间右端点小于当前 $p$ 时弹出。栈顶最大值就是当前 $f(p)$ 。

区间端点都在 $1 \dots n-1$ 内，用两次计数排序代替比较排序，整个询问只需 $O(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
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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

class FastInput {
private:
    static const int BUFFER_SIZE = 1 << 20;
    int position;
    int length;
    char buffer[BUFFER_SIZE];

    char get_char() {
        if (position == length) {
            length = (int)fread(buffer, 1, BUFFER_SIZE, stdin);
            position = 0;
            if (length == 0) return 0;
        }
        return buffer[position++];
    }

public:
    FastInput() : position(0), length(0) {}

    long long read_long_long() {
        char current = get_char();
        while (current <= ' ' && current != 0) current = get_char();

        long long value = 0;
        while (current >= '0' && current <= '9') {
            value = value * 10 + current - '0';
            current = get_char();
        }
        return value;
    }
};

struct Interval {
    int left;
    int right;
    long long value;
};

struct StackNode {
    int right;
    long long maximum;
};

int n;
vector<long long> base_a;
vector<long long> base_b;
vector<long long> a;
vector<long long> b;
vector<long long> prefix_b;
vector<int> previous_ge;
vector<int> next_ge;
vector<Interval> intervals;
vector<int> order_by_right;
vector<int> order_by_left;
vector<int> counter;
vector<StackNode> interval_stack;

void build_nearest_greater() {
    vector<int> stack;
    stack.reserve(n);

    for (int i = 1; i <= n; i++) {
        while (!stack.empty() && a[stack.back()] < a[i]) {
            stack.pop_back();
        }
        if (stack.empty()) previous_ge[i] = 0;
        else previous_ge[i] = stack.back();
        stack.push_back(i);
    }

    stack.clear();
    for (int i = n; i >= 1; i--) {
        while (!stack.empty() && a[stack.back()] < a[i]) {
            stack.pop_back();
        }
        if (stack.empty()) next_ge[i] = n + 1;
        else next_ge[i] = stack.back();
        stack.push_back(i);
    }
}

void build_intervals() {
    intervals.clear();
    intervals.reserve(2 * n);

    for (int i = 1; i <= n; i++) {
        int left = previous_ge[i];
        int right = i - 1;
        if (left < 1) left = 1;
        if (left <= right) {
            long long value = a[i] - (prefix_b[i - 1] - prefix_b[previous_ge[i]]);
            Interval current;
            current.left = left;
            current.right = right;
            current.value = value;
            intervals.push_back(current);
        }

        left = i;
        right = next_ge[i] - 1;
        if (right > n - 1) right = n - 1;
        if (left <= right) {
            long long value = a[i] - (prefix_b[next_ge[i] - 1] - prefix_b[i]);
            Interval current;
            current.left = left;
            current.right = right;
            current.value = value;
            intervals.push_back(current);
        }
    }
}

void sort_intervals() {
    int interval_count = (int)intervals.size();
    order_by_right.resize(interval_count);
    order_by_left.resize(interval_count);

    fill(counter.begin(), counter.end(), 0);
    for (int i = 0; i < interval_count; i++) {
        counter[intervals[i].right]++;
    }

    int position = 0;
    for (int right = n - 1; right >= 1; right--) {
        int count = counter[right];
        counter[right] = position;
        position += count;
    }
    for (int i = 0; i < interval_count; i++) {
        int right = intervals[i].right;
        order_by_right[counter[right]++] = i;
    }

    fill(counter.begin(), counter.end(), 0);
    for (int i = 0; i < interval_count; i++) {
        counter[intervals[order_by_right[i]].left]++;
    }

    position = 0;
    for (int left = 1; left <= n - 1; left++) {
        int count = counter[left];
        counter[left] = position;
        position += count;
    }
    for (int i = 0; i < interval_count; i++) {
        int id = order_by_right[i];
        int left = intervals[id].left;
        order_by_left[counter[left]++] = id;
    }
}

long long calculate_answer() {
    prefix_b[0] = 0;
    for (int i = 1; i <= n; i++) {
        prefix_b[i] = prefix_b[i - 1] + b[i];
    }

    build_nearest_greater();
    build_intervals();
    sort_intervals();

    interval_stack.clear();
    interval_stack.reserve(intervals.size());
    long long answer = 0;
    int interval_count = (int)intervals.size();
    int current_interval = 0;

    for (int split = 1; split <= n - 1; split++) {
        while (!interval_stack.empty() && interval_stack.back().right < split) {
            interval_stack.pop_back();
        }

        while (current_interval < interval_count) {
            int id = order_by_left[current_interval];
            if (intervals[id].left != split) break;

            long long maximum = intervals[id].value;
            if (!interval_stack.empty() && interval_stack.back().maximum > maximum) {
                maximum = interval_stack.back().maximum;
            }
            StackNode node;
            node.right = intervals[id].right;
            node.maximum = maximum;
            interval_stack.push_back(node);
            current_interval++;
        }

        long long value = interval_stack.back().maximum;
        answer ^= value;
    }
    return answer;
}

int main() {
    FastInput input;

    n = (int)input.read_long_long();
    base_a.assign(n + 2, 0);
    base_b.assign(n + 2, 0);
    a.assign(n + 2, 0);
    b.assign(n + 2, 0);
    prefix_b.assign(n + 2, 0);
    previous_ge.assign(n + 2, 0);
    next_ge.assign(n + 2, n + 1);
    counter.assign(n + 2, 0);

    for (int i = 1; i <= n; i++) base_a[i] = input.read_long_long();
    for (int i = 1; i <= n; i++) base_b[i] = input.read_long_long();

    int q = (int)input.read_long_long();
    for (int query = 0; query < q; query++) {
        a = base_a;
        b = base_b;

        int changed = (int)input.read_long_long();
        for (int i = 0; i < changed; i++) {
            int position = (int)input.read_long_long();
            a[position] = input.read_long_long();
            b[position] = input.read_long_long();
        }

        long long answer = calculate_answer();
        printf("%lld\n", answer);
    }

    return 0;
}

复杂度

时间：每次询问复制初始数组并应用 $k$ 个修改后，完成前缀和、两次单调栈、候选区间生成、两次计数排序与区间栈扫描， $O(n + k)$ 。
空间： $O(n)$ 。

总结

核心是把“左右端点交替击杀”转化为贪心过程。一个梦魔只有在两侧更小防御力都被清掉后才成为关键端点，于是它的限制自然对应一个落点区间；最近的不小于自身元素给出区间边界。所有区间具有嵌套结构，最后用栈维护区间最大值即可。

图示解析

这张图串起一次询问从数组到异或答案的主线：

text

1
2
3
4
5
6防御力 a、收益 b
|- 单调栈求每个位置两侧最近的 >= 边界 L、R
   `- 每个梦魔生成至多两个落点限制区间
      |- 区间只能相离或嵌套
      `- 扫描落点，用栈维护覆盖区间的最大限制
         `- 异或所有 f(p)

先由 $L$ 、 $R$ 判断一个梦魔在哪些间隙会成为关键端点，再顺着区间的包含关系观察栈为何只需要保存一条活动链。每个候选区间只入栈、出栈一次，扫描阶段保持线性。

题目来自第 36 次 CSP 认证 T5，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 3.0 秒

空间限制： 512 MB

题目背景

曾经，在西西艾弗岛……

题目描述

有 $n$ 只梦魔会在夜间潜入居民们的梦境世界，让大家整晚做噩梦，无法好好休息。为了西西艾弗岛居民们的幸福，小 C 决定潜入梦魔们的巢穴，向它们发起决斗。

在巢穴里， $n$ 只梦魔站成一列，第 $i$ 只梦魔有防御力 $a_i$ 。如果小 C 的攻击力不严格小于 $a_i$ ，他就可以击杀这只梦魔。由于战斗经验的增长，击杀梦魔之后小 C 的攻击力将上升 $b_i$ 。

因为通往梦魔巢穴的传送门非常不稳定，小 C 可能降落的位置并不确定。具体来说，小 C 会被传送到两只相邻的梦魔之间。每一次进攻时，小 C 可以选择攻击左边或右边离自己最近的梦魔；在击杀一只梦魔之后，与其相邻的梦魔会补上它的位置。

为了确保作战计划万无一失，小 C 想要对于每个位置都求出，如果自己降落在这里，能让他击杀所有梦魔的最小初始攻击力是多少。

由于梦魔们也在成长，所以它们的防御力和击杀带来的收益可能产生细微的变化。在每次变化之后，小 C 依旧想知道每个位置所需的最小初始攻击力。

但小 C 非常菜，于是他只能拜托你帮他解决这个问题了。

输入格式

从标准输入读入数据。

第一行一个正整数 $n$ ，代表梦魔的数量。

第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$ ，其中 $a_i$ 表示第 $i$ 只梦魔的防御力。

第三行 $n$ 个正整数 $b_1,b_2,\dots,b_n$ ，其中 $b_i$ 表示击杀第 $i$ 只梦魔后小 C 攻击力上涨的数值。

第四行一个正整数 $q$ ，表示梦魔的信息发生了 $q$ 次变动。

接下来依次描述 $q$ 次变动，对于每次变动，输入的第一行包含一个非负整数 $k$ ，表示在初始局面中有 $k$ 只梦魔的信息发生了变动。接下来 $k$ 行每行三个正整数 $i,a'_i,b'_i$ ，表示将 $a_i$ 的值修改为 $a'_i$ ， $b_i$ 的值修改为 $b'_i$ 。

注意：每次变动是相互独立的，所有的信息修改都在初始局面中进行。

输出格式

输出到标准输出。

设 $p_i$ 表示小 C 降落在第 $i$ 只梦魔和第 $i+1$ 只梦魔之间时，击杀所有梦魔所需要的最小初始攻击力。

对每次变动输出一行一个整数，表示 $p_1\oplus p_2\oplus \dots \oplus p_{n-1}$ 的值，其中 $\oplus$ 表示按位异或。

input1

1
2
3
4
5
6
7
86
4 9 3 1 7 7
4 2 1 3 1 4
2
2
3 8 1
5 4 3
0

output1

1
29
1

样例 1 解释

第一次变动后有 $p_1=5,p_2=8,p_3=1,p_4=1,p_5=4$ 。

第二次变动后有 $p_1=5,p_2=3,p_3=3,p_4=3,p_5=7$ 。

注意第一次变动对第二次变动不产生影响。

子任务

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务 1（30 分）：保证 $n\le 1000$ ；
子任务 2（40 分）：保证 $n\le 10^5,q\le 5$ ；
子任务 3（10 分）：保证 $1\le a_i,a'_i\le n$ ；
子任务 4（20 分）：无特殊限制。

对于所有数据，保证 $1 \le n \le 2 \times 10^6, 0 \le q \le 20, 1 \le a_i,b_i,a'_i,b'_i \le 10^9$ 。保证所有 $q$ 次变动的 $k$ 之和不大于 $5 \times 10^5$ 。

提示

本题输入量较大，请采用效率较高的读入方式。

梦魔

目录