✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

顺丰

题目一：小毛的数据处理系统

1️⃣：预处理位置前缀数组和值前缀和数组，将大数据流的查询转化为数学计算

2️⃣：使用二分查找快速定位区间端点对应的原始元素

3️⃣：分情况处理查询区间，避免暴力展开超大数组

难度：中等偏难

这道题的核心挑战在于处理超大规模的扩展数据流（最长可达10^10）。通过巧妙的前缀和预处理和二分查找技术，将原本需要O(数组长度)的区间查询转化为O(log n)的高效计算。关键在于理解数据的规律性，利用原始数组的重复特性来避免真实的数组扩展。

题目二：小兰的艺术品收藏

1️⃣：从右往左构建最长无重复后缀，从左往右枚举前缀

2️⃣：使用双指针技术，动态维护前缀和后缀的无重复性

3️⃣：利用哈希集合快速检测元素冲突，确保线性时间复杂度

难度：中等

这道题体现了双指针算法的精妙之处。通过维护两个无重复的端点（前缀和后缀），将原本需要枚举所有可能删除区间的O(n²)暴力方法优化为O(n)的线性算法。关键技巧是理解删除连续子段的本质：保留前后两个无冲突的部分，并通过动态调整来维持这种无冲突性。

01. 小毛的数据处理系统

小毛负责管理公司的数据分析系统。在这个系统中，有一种特殊的数据扩展功能：可以根据重要度权重将原始数据进行复制扩展。

具体来说，系统中有两个配置数组：

• 原始数据数组 ：包含 个数据值
• 权重数组 ：每个位置 的权重 表示对应的数据 需要在扩展后的数据流中重复出现 次

通过这种扩展机制，原始数组 会按顺序扩展成一个更长的数据流 。例如，如果 ，，那么扩展后的数据流就是 。

现在，业务部门需要对这个扩展后的数据流进行多次区间统计查询。小毛需要实现一个高效的查询系统，能够快速计算指定区间内所有数据的总和。

输入格式

第一行包含一个正整数 （），表示原始数据数组的长度。

第二行包含 个正整数 （），表示原始数据数组 。

第三行包含 个正整数 （），表示权重数组 。

第四行包含一个正整数 （），表示查询次数。

接下来 行，第 行包含两个正整数 和 （），表示第 次查询的区间范围。

输出格式

对于每个查询，输出一行整数，表示扩展数据流中指定区间内所有元素的总和。

样例输入

5
8 9 7 5 7
1 2 2 1 3
2
3 7
1 9

样例输出

35
66

数据范围

样例	解释说明
样例1	扩展后数据流为 ，第一次查询区间 对应元素 ，和为

题解

这道题的关键在于理解数据扩展的过程，并且要意识到扩展后的数据流可能非常长（最长可达 ），无法真正存储在内存中。因此需要用前缀和 + 二分查找的方法来高效处理区间查询。

核心思路：

由于扩展后的数据流是按原数组顺序重复生成的，可以通过预处理来快速定位任意位置对应的原始数据。

算法步骤：

1. 预处理阶段：

   • 计算位置前缀数组 pos[i]：表示前 个原始元素在扩展数组中占用的总长度
   • 计算值前缀和数组 sum[i]：表示前 个原始元素贡献的总和（每个元素乘以其重复次数）

2. 查询处理：

   • 对于查询区间 ，使用二分查找在 pos 数组中定位：
     • idL：第一个能覆盖位置 的原始元素下标
     • idR：第一个能覆盖位置 的原始元素下标

3. 分情况计算：

   • 如果 idL == idR：说明查询区间完全在某个原始元素的重复段内，直接计算
   • 否则分三部分计算：左端部分 + 中间完整段 + 右端部分

关键技巧：

• 使用 lower_bound 进行二分查找，快速定位区间端点
• 前缀和技巧避免重复计算中间完整段的贡献
• long long 类型防止数值溢出

时间复杂度： 预处理 ，每次查询 ，总体

这种方法充分利用了数据的规律性，将看似复杂的大数据查询转化为高效的数学计算。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()
import bisect

n = int(input())
a = [0] + list(map(int, input().split()))  # 1-indexed
b = [0] + list(map(int, input().split()))

# 预处理前缀数组
pos = [0] * (n + 1)  # pos[i]表示前i个元素的总长度
val_sum = [0] * (n + 1)  # val_sum[i]表示前i个元素的总贡献

for i in range(1, n + 1):
    pos[i] = pos[i - 1] + b[i]
    val_sum[i] = val_sum[i - 1] + a[i] * b[i]

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    
    # 二分找到覆盖l和r的原始元素位置
    id_l = bisect.bisect_left(pos[1:], l) + 1
    id_r = bisect.bisect_left(pos[1:], r) + 1
    
    # 如果在同一个重复段内
    if id_l == id_r:
        print((r - l + 1) * a[id_l])
        continue
    
    # 分三段计算
    ans = 0
    # 左端：从l到pos[id_l]的部分
    ans += (pos[id_l] - l + 1) * a[id_l]
    # 右端：从pos[id_r-1]+1到r的部分  
    ans += (r - pos[id_r - 1]) * a[id_r]
    # 中间：完整的重复段
    ans += val_sum[id_r - 1] - val_sum[id_l]
    
    print(ans)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<ll> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    
    // 构建前缀数组
    vector<ll> pos(n + 1), val_sum(n + 1);
    for (int i = 1; i <= n; i++) {
        pos[i] = pos[i - 1] + b[i];
        val_sum[i] = val_sum[i - 1] + a[i] * b[i];
    }
    
    int q;
    cin >> q;
    
    while (q--) {
        ll l, r;
        cin >> l >> r;
        
        // 二分查找对应的原始元素下标
        int id_l = lower_bound(pos.begin() + 1, pos.end(), l) - pos.begin();
        int id_r = lower_bound(pos.begin() + 1, pos.end(), r) - pos.begin();
        
        if (id_l == id_r) {
            // 区间完全在同一重复段内
            cout << (r - l + 1) * a[id_l] << "\n";
            continue;
        }
        
        ll ans = 0;
        // 左端部分贡献
        ans += (pos[id_l] - l + 1) * a[id_l];
        // 右端部分贡献
        ans += (r - pos[id_r - 1]) * a[id_r];
        // 中间完整段贡献
        ans += val_sum[id_r - 1] - val_sum[id_l];
        
        cout << ans << "\n";
    }
    
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        long[] dataVals = new long[n + 1];  // 原始数据值
        long[] weights = new long[n + 1];   // 权重值
        
        String[] aStr = br.readLine().split(" ");
        String[] bStr = br.readLine().split(" ");
        
        for (int i = 1; i <= n; i++) {
            dataVals[i] = Long.parseLong(aStr[i - 1]);
            weights[i] = Long.parseLong(bStr[i - 1]);
        }