音乐会

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

把 hh:mm:ss 折成秒,对 5 种乐器各开一个差分数组做区间加一,前缀和还原每秒演奏状态,询问时按 PVCDB 拼字符。

OJ: roj

题目 ID: 1994

难度:普及-

标签:差分前缀和python

创建: 2026-10-08 06:59

更新: 2026-10-08 06:59

形式化题目

乐器只有 5 种,编号顺序固定为 P、V、C、D、B。音乐会从 00:00:00 开始, 时刻 hh:mm:ss 代表从这一秒到下一秒的一整秒时间片,因此可以把它唯一地折成一个整数

t=3600 hh+60 mm+ss.t = 3600\,hh + 60\,mm + ss .

由数据范围 0⩽hh⩽90 \leqslant hh \leqslant 9、0⩽mm,ss⩽590 \leqslant mm, ss \leqslant 59 知 t∈[0,35999]t \in [0, 35999],时间轴的总长度只有 36000 个点。

输入给出 nn 条演奏记录,每条形如 l r T(l,rl, r 是时间,TT 是乐器字母), 含义是乐器 TT 在闭区间 [l,r][l, r] 的每一个秒时刻都在演奏。 随后给出 mm 个询问时刻 q1,…,qmq_1, \dots, q_m,对每个 qq 输出一个字符串:

  • 把在 qq 时刻演奏的所有乐器按 PVCDB 顺序拼起来,字母之间不加空格;
  • 若一个乐器也没有,输出 None。

规模:1⩽n,m⩽200001 \leqslant n, m \leqslant 20000(30% 的数据额外满足 hh=0hh = 0)。

正解

思路

朴素做法。 最直接的写法是「每个询问扫一遍全部记录」:对询问时刻 qq,遍历 nn 条记录,看是否有 li⩽q⩽ril_i \leqslant q \leqslant r_i,把命中的乐器标出来再拼字符串。 单次询问 O(n)O(n),总复杂度 O(nm)O(nm)。在 n=m=20000n = m = 20000 时是 4×1084 \times 10^8 次比较, 1000 ms 的时限下很容易 TLE。

瓶颈在哪? 慢不是因为「区间判断」这一步本身贵,而是因为我们把同样的区间 重复检查了 mm 遍。mm 次询问之间没有任何信息复用,每一次都从零开始。 而真正需要的信息很小:对每个时刻,只要知道「哪几种乐器在响」。

关键观察:时间轴极短,应当先离线预处理,再 O(1)O(1) 回答。 若时间是对 10910^9 取值的,就必须上离散化 + 线段树。但这道题有 hh⩽9hh \leqslant 9,于是 tt 的取值只有 3600036000 个。把 nn 条区间记录和 mm 次询问放在一起看, 就是典型的「区间加、单点查询」:

  • 区间加 n⩽20000n \leqslant 20000 次,但每次都作用在一条只有 36000 长的数轴上;
  • 既然值域这么小,与其用线段树,不如直接把整条数轴的状态算出来—— 一维差分数组正是为此而生。

先把区间加变成两个单点操作。 对区间 [l,r][l, r] 加一,只需在差分数组上做 diff[l] += 1; diff[r + 1] -= 1,再做一次前缀和就能还原出每个时刻被覆盖的次数。 注意这里是闭区间:hh:mm:ss 表示「从这一秒到下一秒」的那一秒, 所以右端点 rr 本身要算进去,减一的位置是 r+1r + 1。若 r=35999r = 35999 则 r+1=36000r + 1 = 36000, 差分数组要开到 36000 这一格。

5 种乐器就是 5 条独立的数轴。 每条差分数组只记录一种乐器的覆盖次数, 互不干扰。前缀和还原后,cover[k][t] > 0 就表示乐器 kk 在时刻 tt 正在演奏; 条件必须是 > 0 而不是 == 1——题面提示「两位朋友提供的资料可能会出现重叠」, 同一乐器同一秒可能被多条记录覆盖,计数会大于 1。

单次询问 O(1)O(1)。 询问时刻 qq 折成秒后,依次检查 k=0,1,2,3,4k = 0, 1, 2, 3, 4 对应的 cover[k][q],把大于 0 的乐器字母追加到结果里。因为 kk 的枚举顺序就是 P, V, C, D, B,拼出来的字符串天然满足题目要求的 PVCDB 顺序。 一个都没有命中时输出 None。

以样例为例:把 5 条记录折成秒分别是 [2,5]P、[9,9]V、[4,7]P、[1,2]V、[5,6]V。 在差分上做完前缀和后,t=2t = 2 处 P 与 V 都在响(输出 PV), t=4t = 4 处只有 P(输出 P),t=6t = 6 处两条 V 记录重叠、计数为 2,仍然输出 PV。

Python 版与 C++ 版是同一个算法:C++ 用 int diff[5][36005] 做差分 + 前缀和, Python 用 5 行 list + itertools.accumulate,只是把「每一秒的 5 个计数」 进一步压成一个 5 位的整数掩码 mask[t],把询问阶段的 5 次判断缩成一次按位扫描。

代码

Python 版:

python
#!/usr/bin/env python3
# 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-10-08 06:59
# update_at: 2026-10-08 06:59

import sys
from itertools import accumulate

NAME = "PVCDB"                      # 输出优先级顺序;位 i(i 从 0 起)对应 NAME[i] 这件乐器
MAXT = 9 * 3600 + 59 * 60 + 59      # 题目给的 hh<=9,最大秒 35999,时间轴只有 36000 秒
LEN = MAXT + 2                      # 差分要在 r+1<=36000 处减一,故多留两格

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type DiffTable = list[list[int]]    # 每件乐器一条差分数组,行下标 = 乐器编号


def to_sec(token: str) -> int:
    """把 hh:mm:ss 折成绝对秒,即 3600*hh + 60*mm + ss。"""
    hh, mm, ss = token.split(':')
    return int(hh) * 3600 + int(mm) * 60 + int(ss)


def build_mask(diff: DiffTable) -> list[int]:
    """差分数组求前缀和,还原成"每一秒的乐器掩码":位 i 为 1 表示该秒有 NAME[i] 在响。"""
    mask = [0] * LEN
    for instrument, row in enumerate(diff):
        bit = 1 << instrument
        for t, cover in enumerate(accumulate(row)):   # cover = 该秒被多少条记录覆盖
            if cover > 0:                             # 多条记录重叠,只要非零就算在演奏
                mask[t] |= bit
    return mask


def render(mask: int) -> str:
    """把某一秒的掩码渲染成一行答案:按 PVCDB 顺序拼字母,无人演奏则 None。"""
    return ''.join(ch for i, ch in enumerate(NAME) if mask >> i & 1) or "None"


def solve() -> None:
    tokens = iter(sys.stdin.buffer.read().decode().split())

    n = int(next(tokens))
    diff: DiffTable = [[0] * LEN for _ in range(5)]
    for _ in range(n):
        left = to_sec(next(tokens))
        right = to_sec(next(tokens))
        instrument = NAME.index(next(tokens))
        diff[instrument][left] += 1        # 闭区间 [left, right] 区间加一
        diff[instrument][right + 1] -= 1

    mask = build_mask(diff)

    m = int(next(tokens))
    times = [to_sec(next(tokens)) for _ in range(m)]
    print('\n'.join(render(mask[t]) for t in times))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

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-10-08 06:59
 * update_at: 2026-10-08 06:59
 *
 * 1994《音乐会》:n 条闭区间演奏记录(5 种乐器)+ m 次单点询问,
 * 每种乐器一个差分数组,区间加 1 后前缀和还原,单点询问 O(1) 拼出 PVCDB。
 * 时间折成秒:t = 3600*hh + 60*mm + ss,由 0<=hh<=9 知 t 最大 35999。
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXT = 36000;     // 秒 0..35999,差分还要用 t = 36000 这一格
const int MAXN = 20005;

int diff[5][MAXT + 5];      // 每种乐器的差分数组,下标 0..36000
int state[5][MAXT + 5];     // 前缀和还原后:该秒该乐器是否在演奏(>0 即演奏)
const char* name = "PVCDB"; // 输出优先级顺序

/**
 * hh:mm:ss 折成绝对秒。
 */
int to_sec(int hh, int mm, int ss) {
    return hh * 3600 + mm * 60 + ss;
}

/**
 * 读入一个 hh:mm:ss 时间串并折成秒,冒号交给 scanf 吞掉。
 */
int read_time() {
    int hh, mm, ss;
    scanf("%d:%d:%d", &hh, &mm, &ss);
    return to_sec(hh, mm, ss);
}

/**
 * 乐器字母映射成 0..4 的下标,顺序与 name 一致。
 */
int to_id(char c) {
    for (int i = 0; i < 5; ++i) {
        if (name[i] == c) return i;
    }
    return -1;
}

int main() {
    ll n = 0, m = 0;
    scanf("%lld", &n);

    char op[8];
    for (ll i = 0; i < n; ++i) {
        int l = read_time();
        int r = read_time();
        scanf("%s", op);
        int id = to_id(op[0]);
        if (id < 0) continue;
        // 闭区间 [l, r]:l 处 +1,r+1 处 -1;r 最大 35999,故差分开到 36000。
        diff[id][l] += 1;
        diff[id][r + 1] -= 1;
    }

    // 对每种乐器求前缀和,得到每个秒时刻的覆盖层数
    for (int id = 0; id < 5; ++id) {
        int cur = 0;
        for (int t = 0; t <= MAXT; ++t) {
            cur += diff[id][t];
            state[id][t] = cur;
        }
    }

    scanf("%lld", &m);
    for (ll i = 0; i < m; ++i) {
        int t = read_time();
        int cnt = 0;                        // 本时刻演奏中的乐器数
        for (int id = 0; id < 5; ++id) {
            if (state[id][t] > 0) {
                putchar(name[id]);
                ++cnt;
            }
        }
        if (cnt == 0) printf("None");        // 一个乐器都没有
        putchar('\n');
    }
    return 0;
}

复杂度

  • 时间:读入并打差分标记 O(n)O(n);对 5 种乐器各做一遍长度 36000 的前缀和, 即 O(5⋅MAXT)O(5 \cdot \text{MAXT});回答询问 O(m)O(m)(每次 5 次比较)。 总计 O(n+m+5⋅MAXT)O(n + m + 5 \cdot \text{MAXT}),n=m=20000n = m = 20000、MAXT=36000\text{MAXT} = 36000 时 计算量约 3×1053 \times 10^5 次操作,实测 1 ms 量级(限时 1000 ms)。
  • 空间:5×360055 \times 36005 个 int,约 720 KB;Python 版多存一份掩码数组。 两者都远低于 256 MB 限制。
  • 与 C++ 解法的关系:main.cpp 用二维差分数组 + 二维前缀和,Python 版把 「同一秒的 5 个覆盖计数」压成掩码,复杂度同阶且都是 O(n+m+MAXT)O(n + m + \text{MAXT}), 不存在 Python 特有的 TLE 风险。

总结

  • 先看值域,再选数据结构:hh⩽9hh \leqslant 9 把时间轴压到 36000 个点, 这是本题从「离散化 + 线段树」降到「差分 + 前缀和」的唯一原因。 「区间加、单点查」在值域小时不需要任何树。
  • 闭区间的差分要落在 r+1r + 1:题面的 hh:mm:ss 表示整整一秒,右端点必须算进去; 同时差分数组要预留一格承接 r=35999r = 35999 时的 r+1r + 1。
  • mm 次询问共用一次预处理:把 mm 次重复的区间判断换成一次离线前缀和, 是 O(nm)→O(n+m+MAXT)O(nm) \to O(n + m + \text{MAXT}) 的关键一步。
  • 输出顺序来自乐器编号本身:把编号顺序取成 PVCDB 之后,顺序要求就不需要任何 额外排序逻辑,直接按编号从小到大拼接即可。
  • 计数用 > 0 判断:题面明确提示资料可能重叠,同一乐器同一秒可能被多次覆盖。

说明

  • 本题题面与数据均为仓库内重建:素材源目录带有 data.py 生成脚本, data/ 的 10 个测试点由该脚本自造,题面参考自公开博客 (https://www.cnblogs.com/lyc-lb-blogs/p/14969873.html 等)。 因此本题的「官方判题意图」可能与原书存在偏差,上述分析以题面与重建数据为准。
  • std.cpp 与本分析采用同一算法(5 条差分数组 + 前缀和), 已用真实数据编译核对,10 个点全部一致,未发现该标程与题面不符。