哥德尔机

把每次修改化为矩形赋值取最大值,再按两个坐标轴上的左端点关系拆成四类矩形相交查询。

OJ: shumeng

题目 ID: CSP202406E

难度:省选/NOI-

标签:扫描线线段树二维区间

日期: 2026-07-31 16:21

形式化题目

n×nn \times n 的网格上,初始所有权值为 00。两类操作:

  1. 修改:给定矩形 (x1,y1)(x2,y2)(x_1,y_1)-(x_2,y_2) 和值 vv,把矩形内每个格子的权值更新为 max(原权值,v)\max(\text{原权值}, v)
  2. 查询:给定矩形,输出矩形内所有格子权值的最大值。

思路

由于每次修改是把矩形内的权值与 vv 取最大值,一个位置最终的权值等于覆盖它的所有修改矩形中的最大 vv。因此一次查询的答案就是与查询矩形有非空交集的修改矩形的最大 vv

朴素做法:直接维护网格

先看最直观的做法,直接维护 n×nn \times n 的权值表,每次修改和查询都枚举矩形内所有格子。

cpp
/**
 * 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:小数据暴力解,直接维护 n*n 个格子的最终权重。
#include <bits/stdc++.h>
using namespace std;

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

    int dimension, query_count;
    cin >> dimension >> query_count;
    vector<vector<int> > value(dimension + 1, vector<int>(dimension + 1, 0));
    for (int i = 0; i < dimension; i++) {
        int x1, x2, y1, y2, v;
        cin >> x1 >> x2 >> y1 >> y2 >> v;
        for (int x = x1; x <= x2; x++) {
            for (int y = y1; y <= y2; y++) value[x][y] = max(value[x][y], v);
        }
    }

    for (int i = 0; i < query_count; i++) {
        int x1, x2, y1, y2;
        cin >> x1 >> x2 >> y1 >> y2;
        int answer = 0;
        for (int x = x1; x <= x2; x++) {
            for (int y = y1; y <= y2; y++) answer = max(answer, value[x][y]);
        }
        cout << answer << '\n';
    }

    return 0;
}

坐标范围达到 5×1055 \times 10^5 时无法使用,但能帮助验证“取最大值”的核心语义。

把矩形相交拆成四种情况

设修改矩形为 AA,查询矩形为 BB。对一维闭区间 [a1,a2][a_1, a_2][b1,b2][b_1, b_2],它们有交集当且仅当

a1[b1,b2]b1[a1,a2]a_1 \in [b_1, b_2] \quad \text{或} \quad b_1 \in [a_1, a_2]。

分别对 xxyy 两个坐标轴应用这个判断,两个矩形相交的情况正好分成四类:

x 方向 y 方向 需要判断的条件
A.x1A.x_1B.xB.x A.y1A.y_1B.yB.y 修改矩形左下角在查询矩形内
A.x1A.x_1B.xB.x B.y1B.y_1A.yA.y A.x1A.x_1 在查询 x 范围,且 A.yA.y 覆盖查询 y1y_1
B.x1B.x_1A.xA.x A.y1A.y_1B.yB.y 对称情况
B.x1B.x_1A.xA.x B.y1B.y_1A.yA.y 修改矩形覆盖查询左下角

只要满足其中一类,两个矩形就相交;四类都不满足时,至少一个坐标轴上的区间不相交。分别处理四类并取最大值即可。

第一类:左下角点二维最值

把每个修改矩形的左下角 (x1,y1)(x_1, y_1) 看成带权点,权值为 vv。问题变成:查询点集落在矩形 [x1,x2]×[y1,y2][x_1,x_2] \times [y_1,y_2] 内的最大权值。

xx 轴上建线段树,每个节点保存覆盖的所有点,按 yy 排序并建静态 RMQ(ST 表)。查询时分解 xx 区间,再在每个节点内二分出 yy 区间,用 RMQ 取最大值。

第二、三类:一个端点在内,另一个区间覆盖

以第二类为例:修改的 x1x_1 是一个点,修改的 yy 是一个区间,要求 x1x_1 落在查询 xx 区间内,且修改的 yy 区间覆盖查询的 y1y_1

yy 扫描:修改区间在 y1y_1 处加入、在 y2+1y_2+1 处删除;扫到查询的 y1y_1 时,在 xx 轴线段树上查询区间最大值。每个 x1x_1 位置用堆维护当前有效修改的最大 vv,线段树维护所有位置的最大值。

第三类交换 xxyy 后与第二类完全相同,直接复用同一套过程。

第四类:修改矩形覆盖查询左下角

要求修改矩形包含查询点 (B.x1,B.y1)(B.x_1, B.y_1)。按 xx 扫描,保持当前活跃的修改矩形满足 A.x1B.x1A.x2A.x_1 \le B.x_1 \le A.x_2。把它的 yy 区间插入线段树:对区间分解得到的每个节点放入一个按 vv 排序的堆。

查询 B.y1B.y_1 时沿根到叶子的路径检查每个堆顶,取最大值。修改矩形离开扫描线后只标记失效,访问堆顶时惰性删除失效元素,避免显式删除堆中的任意元素。

代码

cpp
/**
 * 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;

struct Rectangle {
    int x1, x2, y1, y2, value;
};

// 线段树节点保存所有落在该 x 子区间内的左下角点,并按 y 排序。
struct PointNode {
    vector<pair<int, int> > points;
    vector<int> rmq;
};

vector<PointNode> point_tree;
vector<vector<pair<int, int> > > point_by_x;
vector<int> logarithm_table;

void build_point_rmq(int node) {
    int length = (int)point_tree[node].points.size();
    if (length == 0) return;
    int level_count = logarithm_table[length] + 1;
    point_tree[node].rmq.assign(length * level_count, 0);
    for (int i = 0; i < length; i++) {
        point_tree[node].rmq[i] = point_tree[node].points[i].second;
    }
    for (int level = 1; level < level_count; level++) {
        int step = 1 << level;
        int half = step >> 1;
        int offset = level * length;
        int previous_offset = (level - 1) * length;
        for (int i = 0; i + step <= length; i++) {
            point_tree[node].rmq[offset + i] = max(point_tree[node].rmq[previous_offset + i],
                                                    point_tree[node].rmq[previous_offset + i + half]);
        }
    }
}

void build_point_tree(int node, int left, int right) {
    if (left == right) {
        point_tree[node].points = point_by_x[left];
        sort(point_tree[node].points.begin(), point_tree[node].points.end());
        build_point_rmq(node);
        return;
    }
    int middle = (left + right) >> 1;
    build_point_tree(node << 1, left, middle);
    build_point_tree(node << 1 | 1, middle + 1, right);
    vector<pair<int, int> > &first = point_tree[node << 1].points;
    vector<pair<int, int> > &second = point_tree[node << 1 | 1].points;
    point_tree[node].points.reserve(first.size() + second.size());
    merge(first.begin(), first.end(), second.begin(), second.end(),
          back_inserter(point_tree[node].points));
    build_point_rmq(node);
}

int query_point_node(int node, int y1, int y2) {
    vector<pair<int, int> > &points = point_tree[node].points;
    if (points.empty()) return 0;
    int left = lower_bound(points.begin(), points.end(), make_pair(y1, -1)) - points.begin();
    int right = upper_bound(points.begin(), points.end(), make_pair(y2, INT_MAX)) - points.begin() - 1;
    if (left > right) return 0;
    int length = right - left + 1;
    int level = logarithm_table[length];
    int offset = level * (int)points.size();
    int step = 1 << level;
    return max(point_tree[node].rmq[offset + left], point_tree[node].rmq[offset + right - step + 1]);
}

int query_point_rectangle(int node, int left, int right, int query_left, int query_right,
                          int y1, int y2) {
    if (query_right < left || right < query_left) return 0;
    if (query_left <= left && right <= query_right) return query_point_node(node, y1, y2);
    int middle = (left + right) >> 1;
    return max(query_point_rectangle(node << 1, left, middle, query_left, query_right, y1, y2),
               query_point_rectangle(node << 1 | 1, middle + 1, right, query_left, query_right, y1, y2));
}

struct CoverUpdate {
    int point, left, right, value;
};

struct CoverQuery {
    int left, right, point, id;
};

struct HeapItem {
    int value, id;

    bool operator<(const HeapItem &other) const {
        if (value != other.value) return value < other.value;
        return id > other.id;
    }
};

struct SweepEvent {
    int coordinate, type, id;
};

bool sweep_event_less(const SweepEvent &first, const SweepEvent &second) {
    if (first.coordinate != second.coordinate) return first.coordinate < second.coordinate;
    return first.type < second.type;
}

vector<priority_queue<HeapItem> > cover_heap;
vector<char> cover_active;
vector<int> cover_segment;
int cover_limit;

void cover_clean(int point) {
    while (!cover_heap[point].empty() && !cover_active[cover_heap[point].top().id]) {
        cover_heap[point].pop();
    }
}

void cover_point_update(int node, int left, int right, int position, int value) {
    if (left == right) {
        cover_segment[node] = value;
        return;
    }
    int middle = (left + right) >> 1;
    if (position <= middle) cover_point_update(node << 1, left, middle, position, value);
    else cover_point_update(node << 1 | 1, middle + 1, right, position, value);
    cover_segment[node] = max(cover_segment[node << 1], cover_segment[node << 1 | 1]);
}

int cover_range_query(int node, int left, int right, int query_left, int query_right) {
    if (query_right < left || right < query_left) return 0;
    if (query_left <= left && right <= query_right) return cover_segment[node];
    int middle = (left + right) >> 1;
    return max(cover_range_query(node << 1, left, middle, query_left, query_right),
               cover_range_query(node << 1 | 1, middle + 1, right, query_left, query_right));
}

void solve_point_interval_cover(const vector<CoverUpdate> &updates,
                                const vector<CoverQuery> &queries, int limit, vector<int> &answer) {
    cover_limit = limit;
    cover_heap.clear();
    cover_heap.resize(limit + 1);
    cover_active.assign(updates.size(), 0);
    cover_segment.assign(4 * limit + 5, 0);
    vector<SweepEvent> events;
    events.reserve(updates.size() * 2 + queries.size());
    for (int i = 0; i < (int)updates.size(); i++) {
        events.push_back({updates[i].left, 1, i});
        events.push_back({updates[i].right + 1, 0, i});
    }
    for (int i = 0; i < (int)queries.size(); i++) events.push_back({queries[i].point, 2, i});
    sort(events.begin(), events.end(), sweep_event_less);
    // 扫描区间的左、右端点,在线段树中维护每个点坐标上的最大权值。
    for (int i = 0; i < (int)events.size(); i++) {
        SweepEvent event = events[i];
        if (event.type == 1) {
            cover_active[event.id] = 1;
            cover_heap[updates[event.id].point].push({updates[event.id].value, event.id});
            int point = updates[event.id].point;
            cover_clean(point);
            cover_point_update(1, 1, cover_limit, point, cover_heap[point].top().value);
        } else if (event.type == 0) {
            cover_active[event.id] = 0;
            int point = updates[event.id].point;
            cover_clean(point);
            int value = cover_heap[point].empty() ? 0 : cover_heap[point].top().value;
            cover_point_update(1, 1, cover_limit, point, value);
        } else {
            int value = cover_range_query(1, 1, cover_limit,
                                          queries[event.id].left, queries[event.id].right);
            answer[queries[event.id].id] = max(answer[queries[event.id].id], value);
        }
    }
}

vector<priority_queue<HeapItem> > stabbing_heap;
vector<char> stabbing_active;
int stabbing_limit;

void add_stabbing_interval(int node, int left, int right, int query_left, int query_right,
                           int value, int id) {
    if (query_right < left || right < query_left) return;
    if (query_left <= left && right <= query_right) {
        stabbing_heap[node].push({value, id});
        return;
    }
    int middle = (left + right) >> 1;
    add_stabbing_interval(node << 1, left, middle, query_left, query_right, value, id);
    add_stabbing_interval(node << 1 | 1, middle + 1, right, query_left, query_right, value, id);
}

int query_stabbing_point(int node, int left, int right, int position) {
    while (!stabbing_heap[node].empty() && !stabbing_active[stabbing_heap[node].top().id]) {
        stabbing_heap[node].pop();
    }
    int result = stabbing_heap[node].empty() ? 0 : stabbing_heap[node].top().value;
    if (left == right) return result;
    int middle = (left + right) >> 1;
    if (position <= middle) return max(result, query_stabbing_point(node << 1, left, middle, position));
    return max(result, query_stabbing_point(node << 1 | 1, middle + 1, right, position));
}

void solve_rectangle_stabbing(const vector<Rectangle> &updates, const vector<Rectangle> &queries,
                              int limit, vector<int> &answer) {
    stabbing_limit = limit;
    stabbing_heap.clear();
    stabbing_heap.resize(4 * limit + 5);
    stabbing_active.assign(updates.size(), 0);
    vector<SweepEvent> events;
    events.reserve(updates.size() * 2 + queries.size());
    for (int i = 0; i < (int)updates.size(); i++) {
        events.push_back({updates[i].x1, 1, i});
        events.push_back({updates[i].x2 + 1, 0, i});
    }
    for (int i = 0; i < (int)queries.size(); i++) events.push_back({queries[i].x1, 2, i});
    sort(events.begin(), events.end(), sweep_event_less);
    // 扫描修改矩形的 x 区间,在线段树节点堆中保存覆盖的 y 区间。
    for (int i = 0; i < (int)events.size(); i++) {
        SweepEvent event = events[i];
        if (event.type == 1) {
            stabbing_active[event.id] = 1;
            add_stabbing_interval(1, 1, stabbing_limit, updates[event.id].y1,
                                  updates[event.id].y2, updates[event.id].value, event.id);
        } else if (event.type == 0) {
            stabbing_active[event.id] = 0;
        } else {
            int value = query_stabbing_point(1, 1, stabbing_limit, queries[event.id].y1);
            answer[event.id] = max(answer[event.id], value);
        }
    }
}

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

    int dimension, query_count;
    cin >> dimension >> query_count;
    vector<Rectangle> updates(dimension);
    for (int i = 0; i < dimension; i++) {
        cin >> updates[i].x1 >> updates[i].x2 >> updates[i].y1 >> updates[i].y2 >> updates[i].value;
    }
    vector<Rectangle> queries(query_count);
    for (int i = 0; i < query_count; i++) {
        cin >> queries[i].x1 >> queries[i].x2 >> queries[i].y1 >> queries[i].y2;
        queries[i].value = 0;
    }

    vector<int> answer(query_count, 0);

    // 情形一:修改矩形左下角落在查询矩形内。
    point_by_x.assign(dimension + 1, vector<pair<int, int> >());
    for (int i = 0; i < dimension; i++) {
        point_by_x[updates[i].x1].push_back(make_pair(updates[i].y1, updates[i].value));
    }
    logarithm_table.assign(dimension + 1, 0);
    for (int i = 2; i <= dimension; i++) logarithm_table[i] = logarithm_table[i >> 1] + 1;
    point_tree.assign(4 * dimension + 5, PointNode());
    build_point_tree(1, 1, dimension);
    for (int i = 0; i < query_count; i++) {
        answer[i] = max(answer[i], query_point_rectangle(1, 1, dimension,
                                                           queries[i].x1, queries[i].x2,
                                                           queries[i].y1, queries[i].y2));
    }
    point_tree.clear();
    point_by_x.clear();

    vector<CoverUpdate> cover_updates(dimension);
    vector<CoverQuery> cover_queries(query_count);

    // 情形二:修改矩形左下角的 x 在查询范围内,修改 y 区间覆盖查询 y1。
    // 情形三:交换 x、y 后执行同样的算法。
    for (int i = 0; i < dimension; i++) {
        cover_updates[i] = {updates[i].x1, updates[i].y1, updates[i].y2, updates[i].value};
    }
    for (int i = 0; i < query_count; i++) {
        cover_queries[i] = {queries[i].x1, queries[i].x2, queries[i].y1, i};
    }
    solve_point_interval_cover(cover_updates, cover_queries, dimension, answer);

    for (int i = 0; i < dimension; i++) {
        cover_updates[i] = {updates[i].y1, updates[i].x1, updates[i].x2, updates[i].value};
    }
    for (int i = 0; i < query_count; i++) {
        cover_queries[i] = {queries[i].y1, queries[i].y2, queries[i].x1, i};
    }
    solve_point_interval_cover(cover_updates, cover_queries, dimension, answer);

    // 情形四:修改矩形覆盖查询矩形的左下角。
    solve_rectangle_stabbing(updates, queries, dimension, answer);
    for (int i = 0; i < query_count; i++) cout << answer[i] << '\n';
    return 0;
}

复杂度

设修改数为 nn、查询数为 mm

  • 左下角点的静态二维结构:预处理 O(nlog2n)O(n \log^2 n),单次查询 O(log2n)O(\log^2 n)
  • 两次“点 + 区间覆盖”扫描线各为 O((n+m)logn)O((n+m)\log n)
  • 矩形覆盖点的扫描线为 O((n+m)logn)O((n+m)\log n),每个区间在线段树中插入 O(logn)O(\log n) 个堆元素;
  • 空间:O(nlog2n+m)O(n \log^2 n + m),静态 RMQ 是主要开销。

总时间复杂度 O(nlog2n+mlog2n)O(n \log^2 n + m \log^2 n)

总结

先把 ReLU 修改化为矩形取最大值,再用“一维区间相交必有一个左端点落在另一个区间内”的性质,把二维矩形相交划分为四种端点关系。每种关系都转化为静态二维点查询,或扫描线配合线段树与堆维护,最终把逐格模拟降到对数级查询。

图示解析

下面的流程只保留从题意化简到四类数据结构查询的主线:

text
矩形修改:V = max(V, v)
|- 两个矩形相交
|  |- A.x1 在 B.x 内
|  |  |- A.y1 在 B.y 内:左下角点二维最值
|  |  `- B.y1 在 A.y 内:扫描 y + x 线段树
|  `- B.x1 在 A.x 内
|     |- A.y1 在 B.y 内:交换 x/y 后扫描
|     `- B.y1 在 A.y 内:扫描 x + y 区间堆
`- 四类答案取最大值

四个叶子分别对应代码中的四次处理;它们覆盖所有相交矩形,且每类只需要维护修改值的最大值。