非遗客流分析：展厅时段人次区间查询 完整解题档案

档案概况

题目、题干与输入输出

正式题面

源文件：official-prompt.md

规则来源

• 赛项说明页码：8
• 训练题主题：非遗客流分析：展厅时段人次区间查询
• 所属赛道：非遗文化赛道

题目背景

非遗展厅需要根据分时段客流数据安排讲解和体验位。为了快速复盘多个时段组合的人次情况，需要支持大量区间查询，并同步定位单个时段中的峰值客流。

任务描述

• 读取所有时段的人次数据并建立支持快速查询的前缀和数组。
• 对每个闭区间查询输出总人次，保证输出顺序与输入查询顺序一致。
• 额外输出人次最高的时段编号和该时段的人次，若并列取编号最小者。

输入格式

1. 第一行输入 n q，表示时段数量和查询数量。
2. 第二行输入 n 个整数 a1..an，表示第 i 个时段的人次。
3. 接下来 q 行每行输入 l r，表示查询闭区间 [l, r] 的总人次。

输出格式

1. 前 q 行依次输出 query_k=区间总人次。
2. 最后一行输出 peak_slot=时段编号 人次。

数据范围与说明

• 1 <= n, q <= 2 * 10^5。
• 0 <= ai <= 10^5。
• 1 <= l <= r <= n。
• 所有区间和都要使用 64 位整数处理。
• 若最大人次时段有多个，取编号最小者。

样例输入

8 3
5 8 6 10 7 9 4 3
1 3
4 6
2 8

样例输出

query_1=19
query_2=26
query_3=47
peak_slot=4 10

样例解释

• 前三个时段的人次之和为 5 + 8 + 6 = 19。
• 第 4 到 6 时段的人次之和为 10 + 7 + 9 = 26。
• 整段最高单时段客流发生在第 4 个时段，人次为 10。

知识点清单

• 前缀和数组的构建方法。
• 区间和公式 pre[r] - pre[l-1] 的使用。
• 1-based 下标和边界处理。
• 64 位整数累计。
• 最大值并列取最早位置的维护。

约束拆解

源文件：parsed-constraints.md

显式约束

• 1 <= n, q <= 2 * 10^5。
• 0 <= ai <= 10^5。
• 1 <= l <= r <= n。
• 所有区间和都要使用 64 位整数处理。
• 若最大人次时段有多个，取编号最小者。

建模拆解

• 先明确输入的实体和字段，再把它们翻译成 前缀和 + 顺序扫描最大值 需要的数据结构。
• 把输出中每一项指标都和中间变量对应起来，避免最后临时拼装。
• 先用样例手推一次，再确认边界条件是否都能走到正确分支。

易错边界

• 查询区间刚好从第 1 个时段开始时，要正确处理 pre[0]。
• 多个时段并列最高时，必须输出编号最小的那个时段。
• 大规模查询下不能退回逐次累加，否则会超时。

计分模型

源文件：scoring-model.md

判题方式

• 主判题方式：exact
• 主算法：前缀和 + 顺序扫描最大值

判题重点

• 重点校验公式、排序规则和格式化输出是否完全一致。
• 隐藏数据会覆盖边界值、重复值和最小规模输入。

公开样例建议

• 至少准备 1 组题面样例、2 组边界样例和 2 组自定义回归样例。
• 多输出题必须验证所有字段都来自同一套方案。

隐藏数据建议

• 准备包含多个查询都覆盖首元素和末元素的用例。
• 准备所有时段人次都相同的用例，检查并列取最早规则。
• 准备单点区间和大区间混合查询，验证公式稳定性。

验收清单

源文件：acceptance-checklist.md

• 正式题面、约束拆解、评分说明均已补齐
• 样例输入输出已定义并通过主实现校验
• python 主实现已提供并与样例输出对齐
• 调试记录、决策记录、验证计划已补齐
• 可由 20-tools/assemble_case_dossiers.py 汇总为完整解题档案

样例输入输出

样例输入：sample.in

8 3
5 8 6 10 7 9 4 3
1 3
4 6
2 8

样例输出：sample.out

query_1=19
query_2=26
query_3=47
peak_slot=4 10

题解、建模与最终解法

自动整理的解题流程

• 题目主题：非遗客流分析：展厅时段人次区间查询
• 题目摘要：对展厅时段人次构建前缀和，快速回答多次区间查询，并找出人次最高的时段。
• 判题提示：该题以精确输出为主，最终程序需要重点保证公式、顺序和格式完全一致。
• 先完成输入、对象、约束和输出的四步建模，再落到具体算法和实现。
• 优先用样例验证最小流程，再补边界测试和错误分支。

解题思路

源文件：solution-rationale.md

1. 问题重述

对展厅时段人次构建前缀和，快速回答多次区间查询，并找出人次最高的时段。

2. 数据结构与建模

• 主算法：前缀和 + 顺序扫描最大值
• 输入拆解后对应的数据结构要和输出项一一对应。
• 需要重点维护的状态包括：题目实体、核心指标、中间结果和最终答案。

3. 算法步骤

1. 先读入所有时段人次，顺序构建前缀和数组。
2. 同步扫描数组，记录最高人次及其最早出现位置。
3. 对每个查询用前缀和在 O(1) 时间得到区间总人次。
4. 按题目格式输出所有查询结果和峰值时段信息。

4. 正确性说明

• 每一步都严格对应题面给出的规则或约束。
• 所有输出字段都来自同一份计算过程，不会出现“各算各的”的不一致情况。
• 边界情况通过单独分支或统一规则处理，保证程序在最小规模和重复值情况下也稳定。

5. 复杂度分析

• 复杂度取决于输入规模和主算法，但整体设计保持在初中组可讲解、可验证的范围内。
• 只保留必要状态，不引入超出题意的数据结构。

6. 易错点

• 查询区间刚好从第 1 个时段开始时，要正确处理 pre[0]。
• 多个时段并列最高时，必须输出编号最小的那个时段。
• 大规模查询下不能退回逐次累加，否则会超时。

7. 知识点清单

• 前缀和数组的构建方法。
• 区间和公式 pre[r] - pre[l-1] 的使用。
• 1-based 下标和边界处理。
• 64 位整数累计。
• 最大值并列取最早位置的维护。

设计决策记录

源文件：decision-log.md

• 选择 前缀和 + 顺序扫描最大值 作为主算法，因为它能直接覆盖题目的核心约束。
• 题目核心是重复区间求和，因此主方案必须把单次查询降到 O(1)。
• 峰值时段和区间查询互不冲突，可以在建表阶段顺手完成统计。
• Python 与 C++ 版本统一输出格式，便于双语训练和证据采集。

验证计划

源文件：validation-plan.md

• 先验证题面公开样例，确保基础流程无误。
• 准备包含多个查询都覆盖首元素和末元素的用例。
• 准备所有时段人次都相同的用例，检查并列取最早规则。
• 准备单点区间和大区间混合查询，验证公式稳定性。
• 最后再补 1 组手工构造的极小数据，确认程序不会依赖特殊输入规模。

备选方案

源文件：alternatives.md

最终代码与实现

Python 主实现

源文件：main.py

• 实现状态：当前已有可执行实现

import sys


def solve(data: str) -> str:
    tokens = list(map(int, data.split()))
    if not tokens:
        return ""
    it = iter(tokens)
    n = next(it)
    q = next(it)
    values = [0] + [next(it) for _ in range(n)]
    prefix = [0] * (n + 1)
    best_slot = 1
    for index in range(1, n + 1):
        prefix[index] = prefix[index - 1] + values[index]
        if values[index] > values[best_slot]:
            best_slot = index
    lines = []
    for query_id in range(1, q + 1):
        left = next(it)
        right = next(it)
        lines.append(f"query_{query_id}={prefix[right] - prefix[left - 1]}")
    lines.append(f"peak_slot={best_slot} {values[best_slot]}")
    return "\n".join(lines)


if __name__ == "__main__":
    sys.stdout.write(solve(sys.stdin.read()).strip())
    sys.stdout.write("\n")

代码执行与运行结果

最新成功运行

PY 运行输出摘录

query_1=19
query_2=26
query_3=47
peak_slot=4 10

全部运行记录索引

调试、修正与流程留痕

调试日志

源文件：debug-journal.md

失败案例目录

源文件：failure-catalog.md

编码过程记录

源文件：implementation-journal.md

全流程文件导航

• 题目总览：s1-jh-05-heritage-traffic-query/README.md
• 题面与约束：official-prompt.md、parsed-constraints.md、scoring-model.md、acceptance-checklist.md
• 代码与样例：10-cases/s1-jh-05-heritage-traffic-query/02-solution
• 运行证据：10-cases/s1-jh-05-heritage-traffic-query/03-execution
• 调试过程：debug-journal.md、failure-catalog.md、implementation-journal.md
• 解法说明：solution-rationale.md、decision-log.md、validation-plan.md、alternatives.md
• 交付档案：final-report.md、appendix-code.md、appendix-runs.md、evidence-pack.md