有编号为 1 到 N 的停车位。每盏灯挂在位置 P 上，照亮从 P - S 到 P + S 的区间，并会被限制在 1..N 范围内。之后有 Q 个查询，每个查询询问某个停车位是否至少被一盏灯照亮。由于 N、L 和 Q 都可能达到 500,000，如果每次查询都逐一检查所有灯会太慢。

核心概念

• 区间覆盖
• 差分数组
• 前缀和
• 预处理后 O(1) 回答查询

思考过程

每盏灯覆盖一个连续区间。对于位置为 P、扩散范围为 S 的灯，计算 left = max(1, P - S)，right = min(N, P + S)。不要逐个标记所有被照亮的位置，而只记录边界变化：在 left 处加 1，在 right 之后减 1。之后通过前缀和即可知道每个停车位被多少盏灯覆盖。如果查询位置的覆盖数大于 0，输出 Y；否则输出 N。

解法一：暴力标记

最直接的想法是把每盏灯覆盖的所有停车位逐个标记出来。这个方法简单，也有助于理解题意，但当 N、L 和 Q 很大时会太慢。

# CCC 2026 J5/S2 - Beams of Light
# Solution #1: Brute Force, Mark every lit spot directly

# Read input
N = int(input())   # number of parking spots
L = int(input())   # number of lights
Q = int(input())   # number of questions

# lit[i] will tell us whether parking spot i is illuminated
# We use size N + 1 so we can use indices 1 to N directly
lit = [False] * (N + 1)

# Process each light
for _ in range(L):
    P, S = map(int, input().split())

    # Find the interval this light covers
    left = max(1, P - S)
    right = min(N, P + S)

    # Mark every spot in this interval as illuminated
    for i in range(left, right + 1):
        lit[i] = True

# Answer each question
for _ in range(Q):
    x = int(input())

    if lit[x]:
        print('Y')
    else:
        print('N')

解法二：差分数组

优化方法只记录每盏灯覆盖区间的起点和终点边界变化。完成一次前缀和后，每个查询都可以 O(1) 回答。

Python 解法

import sys
input = sys.stdin.readline

N = int(input())
L = int(input())
Q = int(input())

diff = [0] * (N + 2)

for _ in range(L):
    P, S = map(int, input().split())
    left = max(1, P - S)
    right = min(N, P + S)
    diff[left] += 1
    diff[right + 1] -= 1

covered = [False] * (N + 1)
current = 0
for i in range(1, N + 1):
    current += diff[i]
    covered[i] = current > 0

answers = []
for _ in range(Q):
    x = int(input())
    answers.append('Y' if covered[x] else 'N')

print('\n'.join(answers))

C++ 解法

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

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

    int N, L, Q;
    cin >> N >> L >> Q;

    vector<int> diff(N + 2, 0);

    for (int i = 0; i < L; i++) {
        int P, S;
        cin >> P >> S;
        int left = max(1, P - S);
        int right = min(N, P + S);
        diff[left]++;
        diff[right + 1]--;
    }

    vector<bool> covered(N + 1, false);
    int current = 0;
    for (int i = 1; i <= N; i++) {
        current += diff[i];
        covered[i] = current > 0;
    }

    while (Q--) {
        int x;
        cin >> x;
        cout << (covered[x] ? 'Y' : 'N') << '\n';
    }

    return 0;
}

复杂度分析

构建差分数组需要 O(L)，计算前缀和需要 O(N)，回答所有查询需要 O(Q)。总时间复杂度为 O(N + L + Q)，空间复杂度为 O(N)。

常见错误

• 逐个标记每盏灯覆盖的所有位置，在范围很大时会太慢。
• 忘记把区间限制在有效范围 1..N 内。
• 忘记在 right + 1 处做 -1 更新。
• 对灯和查询使用嵌套循环。

学习成果

• 识别区间覆盖类问题。
• 使用差分数组高效处理大量区间更新。
• 使用前缀和把边界变化转换为实际覆盖情况。
• 通过一次预处理，让每个查询都能 O(1) 回答。