笔试时间：2025年8月23日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：静止俄罗斯方块

相信大家都玩过俄罗斯方块，本题提供一个新版供大家体验 —— 静止版俄罗斯方块，简单规则如下：

游戏为玩家提供一个高度无限，宽度为 n 的界面，并且具有一个初始状态，包含 n 列不可破坏的方块，每一列宽度为 1，高度为 ai；游戏开始后，会有 m 个矩形方块依次贴着界面最左边从无限高处下落，每个方块宽 wi 高 hi；和传统的俄罗斯方块游戏一样，一旦下落的矩形方块碰到任意方块，就会立即停止下落。遗憾的是，正如游戏的名字一样，在这个过程中玩家无法进行对方块进行任何操作，但是游戏换了一个玩法：请玩家回答游戏过程中每个下落的矩形方块在停止下落后底部的高度是多少。

输入描述

第一行输入一个正整数 n（1 ≤ n ≤ 100000），表示游戏界面宽度。

第二行输入 n 个正整数 ai（1 ≤ ai ≤ 10 的 9 次方，a1 ≤ a2 ≤ … ≤ an），表示游戏初始状态。

第三行输入一个正整数 m，表示游戏过程中下落的矩形方块个数。

接下来 m 行，每行包含两个数字 wi 和 hi（1 ≤ wi ≤ n，1 ≤ hi ≤ 10 的 9 次方），中间用空格隔开，代表一个方块的宽和高。

输出描述

一共输出 m 行答案，代表每个方块底部所处的高度。

样例输入

5

1 2 3 6 6

4

1 1

3 1

1 1

4 3

样例输出

1

3

4

6

参考题解

对于每一个下落的方块（宽度为 w），我们需要做两件事：查询：找到它将覆盖的列（第 1 到 w 列）中，当前最高的障碍物高度。更新：方块落下后，它覆盖的所有列（第 1 到 w 列）的高度都会变成一个新的、统一的高度。这两个核心操作本质上是数据结构中的经典问题：范围最大值查询。如果用普通数组模拟，每次查询和更新都需要遍历 w 个元素，时间复杂度为 O(w)。总复杂度为 O(m×n)，对于 10^5 的数据规模来说，这必然会超时。能够同时高效处理“范围查询”和“范围更新”的数据结构是 线段树。它可以在 O(logn) 时间内完成一次范围查询。借助懒惰标记，它同样可以在 O(logn) 时间内完成一次范围更新。用初始的 n 列高度构建一个线段树。对于 m 个方块，依次执行以下步骤： a.  在线段树上查询区间 [1, w] 的最大值，此即为方块底部高度。 b.  计算出新高度后，在线段树上对区间 [1, w] 进行范围更新。

C++：

#include <bits/stdc++.h>
using namespace std;

struct SegmentTree {
    int n;
    vector<long long> tree, lazy; // using long long to be safe with heights

    SegmentTree(int size, const vector<long long>& a) : n(size) {
        tree.assign(4 * n + 4, 0);
        lazy.assign(4 * n + 4, 0);
        build(1, 1, n, a);
    }

    void build(int node, int start, int end, const vector<long long>& a) {
        if (start == end) {
            tree[node] = a[start - 1];
            return;
        }
        int mid = start + (end - start) / 2;
        build(node * 2, start, mid, a);
        build(node * 2 + 1, mid + 1, end, a);
        tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }

    void push_down(int node, int start, int end) {
        if (lazy[node] == 0 || start == end) return;
        tree[node * 2] = lazy[node];
        tree[node * 2 + 1] = lazy[node];
        lazy[node * 2] = lazy[node];
        lazy[node * 2 + 1] = lazy[node];
        lazy[node] = 0;
    }

    void update(int node, int start, int end, int l, int r, long long val) {
        push_down(node, start, end);
        if (start > r || end < l) return;
        if (l <= start && end <= r) {
            tree[node] = val;
            lazy[node] = val;
            return;
        }
        int mid = start + (end - start) / 2;
        update(node * 2, start, mid, l, r, val);
        update(node * 2 + 1, mid + 1, end, l, r, val);
        tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }

    long long query(int node, int start, int end, int l, int r) {
        if (start > r || end < l) return 0;
        push_down(node, start, end);
        if (l <= start && end <= r) return tree[node];
        int mid = start + (end - start) / 2;
        long long p1 = query(node * 2, start, mid, l, r);
        long long p2 = query(node * 2 + 1, mid + 1, end, l, r);
        return max(p1, p2);
    }

    // Convenience wrappers
    void updateRange(int l, int r, long long val) { update(1, 1, n, l, r, val); }
    long long queryRange(int l, int r) { return query(1, 1, n, l, r); }
};

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

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int m; cin >> m;

    SegmentTree seg(n, a);

    string out; out.reserve(m * 2); // rough reserve
    for (int i = 0; i < m; ++i) {
        int w; long long h;
        cin >> w >> h;
        long long max_h = seg.queryRange(1, w);
        out += to_string(max_h);            // no separator/newline, matches Python
        long long new_h = max_h + h;
        seg.updateRange(1, w, new_h);
    }
    cout << out;
    return 0;
}

Java：

import java.io.*;
import java.util.*;

public class Main {
    static class SegmentTree {
        int n;
        long[] tree, lazy;

        SegmentTree(int size, long[] a) {
            this.n = size;
            int cap = 4 * n + 4;
            tree = new long[cap];
            lazy = new long[cap];
            build(1, 1, n, a);
        }

        void build(int node, int start, int end, long[] a) {
            if (start == end) {
                tree[node] = a[start - 1];
                return;
            }
            int mid = start + (end - start) / 2;
            build(node * 2, start, mid, a);
            build(node * 2 + 1, mid + 1, end, a);
            tree[node] = Math.max(tree[node * 2], tree[node * 2 + 1]);
        }

        void pushDown(int node, int start, int end) {
            if (lazy[node] == 0 || start == end) return;
            tree[node * 2] = lazy[node];
            tree[node * 2 + 1] = lazy[node];
            lazy[node * 2] = lazy[node];
            lazy[node * 2 + 1] = lazy[node];
            lazy[node] = 0;
        }

        void update(int node, int start, int end, int l, int r, long val) {
            pushDown(node, start, end);
            if (start > r || end < l) return;
            if (l <= start && end <= r) {
                tree[node] = val;
                lazy[node] = val;
                return;
            }
            int mid = start + (end - start) / 2;
            update(node * 2, start, mid, l, r, val);
            update(node * 2 + 1, mid + 1, end, l, r, val);
            tree[node] = Math.max(tree[node * 2], tree[node * 2 + 1]);
        }

        long query(int node, int start, int end, int l, int r) {
            if (start > r || end < l) return 0;
            pushDown(node, start, end);
            if (l <= start && end <= r) return tree[node];
            int mid = start + (end - start) / 2;
            long p1 = query(node * 2, start, mid, l, r);
            long p2 = query(node * 2 + 1, mid + 1, end, l, r);
            return Math.max(p1, p2);
        }

        void updateRange(int l, int r, long val) { update(1, 1, n, l, r, val); }
        long queryRange(int l, int r) { return query(1, 1, n, l, r); }
    }

    // Fast scanner
    static class FastScanner {
        BufferedInputStream in = new BufferedInputStream(System.in);
        byte[] buffer = new byte[1 << 16];
        int ptr = 0, len = 0;

        int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        String next() throws IOException {
            StringBuilder sb = new StringBuilder();
            int c;
            wh