题解 | #小红的慕斯模具统计#

题目链接

题目描述

小红经营着一家烘焙坊，共有 $N$ 种款式的慕斯模具（编号 $1$ 到 $N$ ）。流水线上记录了 $M$ 次模具的使用信息，第 $j$ 次记录显示，在时间点 $T_j$ 使用了编号为 $ID_j$ 的模具。小红提出了 $Q$ 个查询。每个查询由起始时间 $L_i$ 和固定时间跨度 $W$ 组成，代表观察的时间区间为 $[L_i, L_i + W - 1]$ （即从 $L_i$ 开始持续 $W$ 个单位时间）。对于每个查询，需要计算在该时间区间内使用了多少种不同编号的模具。

解题思路

本题是一个区间不同元素计数问题。由于查询的时间跨度 $W$ 是固定的，且所有查询区间具有相同的长度，我们可以通过**滑动窗口（双指针）**来高效解决。

数据组织与排序：
- 根据样例说明，记录的输入格式为 ID Time。
- 将所有使用记录 $(T_j, ID_j)$ 按照时间点 $T_j$ 进行升序排序。
- 将查询离线处理：将查询起始时间 $L_i$ 与原始索引 $idx$ 绑定，并按照 $L_i$ 进行升序排序。
滑动窗口逻辑：
- 使用两个指针 left_ptr 和 right_ptr 维护当前窗口 $[L_i, L_i + W - 1]$ 内的使用记录。
- 随着 $L_i$ 增加，窗口的左右边界单调右移。
- 右边界扩展：将所有满足 $T_j \le L_i + W - 1$ 的记录加入窗口，并更新模具频次。
- 左边界收缩：将所有满足 $T_j < L_i$ 的记录移出窗口，并更新模具频次。
计数维护：
- 由于模具编号 $ID$ 可能非常大（高达 $10^9$ ），直接使用数组会越界。在 C++ 和 Java 中，我们使用映射表（map 或 HashMap）来记录窗口内每种模具的频次。
- 使用变量 $distinct\_count$ 记录当前窗口内不同模具的种类数。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

// 记录结构体
struct Record {
    int t, id;
};

// 查询信息结构体
struct Query {
    int l, idx;
};

int main() {
    int n, w, q;
    cin >> n >> w >> q;

    vector<Query> queries(q);
    for (int i = 0; i < q; ++i) {
        int l;
        cin >> l;
        queries[i] = {l, i};
    }

    int m;
    cin >> m;
    vector<Record> records(m);
    for (int i = 0; i < m; ++i) {
        int id, t;
        // 注意：根据样例，输入格式为 ID Time
        cin >> id >> t;
        records[i] = {t, id};
    }

    // 预处理：按时间排序
    sort(records.begin(), records.end(), [](const Record& a, const Record& b) {
        return a.t < b.t;
    });
    sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
        return a.l < b.l;
    });

    vector<int> ans(q);
    map<int, int> cnt; // 使用 map 处理可能的大 ID
    int distinct_count = 0;
    int left_ptr = 0, right_ptr = 0;

    for (int i = 0; i < q; ++i) {
        int L = queries[i].l;
        int R = L + w - 1;

        // 移入右边界
        while (right_ptr < m && records[right_ptr].t <= R) {
            int mid = records[right_ptr].id;
            if (cnt[mid] == 0) distinct_count++;
            cnt[mid]++;
            right_ptr++;
        }
        // 移出左边界
        while (left_ptr < m && records[left_ptr].t < L) {
            int mid = records[left_ptr].id;
            cnt[mid]--;
            if (cnt[mid] == 0) distinct_count--;
            left_ptr++;
        }
        ans[queries[i].idx] = distinct_count;
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << (i == q - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.*;

public class Main {
    static class Record {
        int t, id;
        Record(int t, int id) {
            this.t = t;
            this.id = id;
        }
    }

    static class Query {
        int l, idx;
        Query(int l, int idx) {
            this.l = l;
            this.idx = idx;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int w = sc.nextInt();
        int q = sc.nextInt();

        Query[] queries = new Query[q];
        for (int i = 0; i < q; i++) {
            queries[i] = new Query(sc.nextInt(), i);
        }

        int m = sc.nextInt();
        Record[] records = new Record[m];
        for (int i = 0; i < m; i++) {
            int id = sc.nextInt();
            int t = sc.nextInt();
            records[i] = new Record(t, id);
        }

        // 排序
        Arrays.sort(records, (a, b) -> Integer.compare(a.t, b.t));
        Arrays.sort(queries, (a, b) -> Integer.compare(a.l, b.l));

        int[] ans = new int[q];
        Map<Integer, Integer> cnt = new HashMap<>();
        int distinctCount = 0;
        int leftPtr = 0;
        int rightPtr = 0;

        for (int i = 0; i < q; i++) {
            int L = queries[i].l;
            int R = L + w - 1;

            while (rightPtr < m && records[rightPtr].t <= R) {
                int id = records[rightPtr].id;
                int currentCnt = cnt.getOrDefault(id, 0);
                if (currentCnt == 0) distinctCount++;
                cnt.put(id, currentCnt + 1);
                rightPtr++;
            }
            while (leftPtr < m && records[leftPtr].t < L) {
                int id = records[leftPtr].id;
                int currentCnt = cnt.get(id);
                if (currentCnt == 1) {
                    distinctCount--;
                    cnt.remove(id);
                } else {
                    cnt.put(id, currentCnt - 1);
                }
                leftPtr++;
            }
            ans[queries[i].idx] = distinctCount;
        }

        for (int i = 0; i < q; i++) {
            System.out.print(ans[i] + (i == q - 1 ? "" : " "));
        }
        System.out.println();
    }
}

def solve():
    # 输入读取
    line1 = input().split()
    n, w, q = map(int, line1)
    
    l_list = list(map(int, input().split()))
    queries = []
    for i in range(q):
        queries.append([l_list[i], i])
    
    m = int(input())
    records = []
    for _ in range(m):
        # 样例说明表明输入格式为 ID Time
        mid, t = map(int, input().split())
        records.append([t, mid])
    
    # 离线处理：按时间排序
    records.sort()
    queries.sort()
    
    ans = [0] * q
    cnt = {} # 使用字典处理可能的大 ID
    distinct_count = 0
    left_ptr = 0
    right_ptr = 0
    
    for l, idx in queries:
        r = l + w - 1
        
        # 移动右指针扩展窗口
        while right_ptr < m and records[right_ptr][0] <= r:
            mid = records[right_ptr][1]
            if cnt.get(mid, 0) == 0:
                distinct_count += 1
            cnt[mid] = cnt.get(mid, 0) + 1
            right_ptr += 1
            
        # 移动左指针收缩窗口
        while left_ptr < m and records[left_ptr][0] < l:
            mid = records[left_ptr][1]
            cnt[mid] -= 1
            if cnt[mid] == 0:
                distinct_count -= 1
            left_ptr += 1
            
        ans[idx] = distinct_count
        
    print(*(ans))

solve()

算法及复杂度

算法：滑动窗口（双指针） + 离线查询。
时间复杂度： $\mathcal{O}(M \log M + Q \log Q)$ 。排序占主导地位，滑动窗口过程为线性扫过记录和查询列表。
空间复杂度： $\mathcal{O}(N + M + Q)$ 。需要存储记录、查询及每种模具的频次。