方法思路

这道题目可以使用差分数组来高效解决。差分数组是一种常用的技巧，可以将区间更新操作转化为两个点的更新操作。

1. 创建一个差分数组diff，长度为N+1，初始值全为0
2. 对于每次陨石坠落区间[L,R]：
   • 将diff[L]增加1，表示从位置L开始，每个位置的打击次数增加1
   • 将diff[R+1]减少1，表示从位置R+1开始，打击次数的增量结束
3. 计算前缀和：从左到右遍历差分数组，得到每个位置的实际打击次数
4. 对于每个查询位置x，直接返回对应的前缀和值

代码实现

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] firstLine = br.readLine().split(" ");
        int N = Integer.parseInt(firstLine[0]);
        int M = Integer.parseInt(firstLine[1]);
        
        // 读取左边界
        String[] leftBounds = br.readLine().split(" ");
        int[] L = new int[M];
        for (int i = 0; i < M; i++) {
            L[i] = Integer.parseInt(leftBounds[i]);
        }
        
        // 读取右边界
        String[] rightBounds = br.readLine().split(" ");
        int[] R = new int[M];
        for (int i = 0; i < M; i++) {
            R[i] = Integer.parseInt(rightBounds[i]);
        }
        
        // 创建差分数组
        int[] diff = new int[N + 2]; // 多一个位置处理R+1
        
        // 处理每次陨石坠落
        for (int i = 0; i < M; i++) {
            diff[L[i]]++;       // 区间开始位置增加1
            diff[R[i] + 1]--;   // 区间结束位置的下一个位置减少1
        }
        
        // 计算前缀和，得到每个位置的打击次数
        int[] hits = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            hits[i] = (i == 0) ? diff[i] : hits[i-1] + diff[i];
        }
        
        // 处理查询
        int Q = Integer.parseInt(br.readLine());
        String[] queries = br.readLine().split(" ");
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < Q; i++) {
            int x = Integer.parseInt(queries[i]);
            sb.append(hits[x]);
            if (i < Q - 1) sb.append(" ");
        }
        
        bw.write(sb.toString());
        bw.flush();
    }
}

Python

def main():
    # 读取输入
    N, M = map(int, input().split())
    L = list(map(int, input().split()))
    R = list(map(int, input().split()))
    Q = int(input())
    queries = list(map(int, input().split()))
    
    # 创建差分数组
    diff = [0] * (N + 2)
    
    # 处理每次陨石坠落
    for i in range(M):
        diff[L[i]] += 1      # 区间开始位置增加1
        diff[R[i] + 1] -= 1  # 区间结束位置的下一个位置减少1
    
    # 计算前缀和，得到每个位置的打击次数
    hits = [0] * (N + 1)
    for i in range(N + 1):
        hits[i] = diff[i] if i == 0 else hits[i-1] + diff[i]
    
    # 处理查询并输出结果
    results = [hits[x] for x in queries]
    print(' '.join(map(str, results)))

if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    // 读取左边界
    vector<int> L(M);
    for (int i = 0; i < M; i++) {
        cin >> L[i];
    }
    
    // 读取右边界
    vector<int> R(M);
    for (int i = 0; i < M; i++) {
        cin >> R[i];
    }
    
    // 创建差分数组
    vector<int> diff(N + 2, 0);
    
    // 处理每次陨石坠落
    for (int i = 0; i < M; i++) {
        diff[L[i]]++;       // 区间开始位置增加1
        diff[R[i] + 1]--;   // 区间结束位置的下一个位置减少1
    }
    
    // 计算前缀和，得到每个位置的打击次数
    vector<int> hits(N + 1);
    hits[0] = diff[0];
    for (int i = 1; i <= N; i++) {
        hits[i] = hits[i-1] + diff[i];
    }
    
    // 处理查询
    int Q;
    cin >> Q;
    
    for (int i = 0; i < Q; i++) {
        int x;
        cin >> x;
        cout << hits[x];
        if (i < Q - 1) cout << " ";
    }
    cout << endl;
    
    return 0;
}