小红的慕斯模具统计

[题目链接](https://www.nowcoder.com/practice/c016abeeac86418db4ae97319de04af5)

思路

本题需要对多个等长的时间区间查询，统计每个区间内使用过的不同模具种类数。

离线排序 + 双指针

注意到所有查询的时间窗口宽度都是 ，这意味着如果我们按起始时间排序所有查询，那么每个窗口的左端点 和右端点 都是单调不减的。这正是双指针（滑动窗口）的经典适用场景。

具体步骤：

  1. 预处理记录：将所有使用记录按时间排序。
  2. 离线排序查询：将所有查询按起始时间排序，同时记录原始下标，以便最后按原始顺序输出答案。
  3. 双指针滑动：维护两个指针 lo 和 hi，分别表示当前窗口在排序记录中的左右边界。对于每个查询 ：

- 先右扩：将 hi 向右推进，加入所有时间 的记录。

- 再左缩：将 lo 向右推进，移除所有时间 的记录。

  1. 计数：用一个数组 cnt[mold] 记录每种模具在当前窗口中出现的次数，用变量 distinct 维护当前窗口中不同模具的种类数。当某种模具的计数从 0 变为 1 时，distinct 加 1；从 1 变为 0 时，distinct 减 1。

为什么要先加后删？ 如果先删后加，当两个相邻查询之间存在跳跃（即有些记录的时间落在上一个窗口的右端点和当前窗口的左端点之间），lo 可能会越过 hi，导致尝试移除从未被加入窗口的记录。先加后删则不会出现这个问题。

举例

以样例为例，，起始时间 ，4 条记录（模具 时间）：。

按时间排序后的记录：。

查询按起始时间排序：。

查询 窗口 加入的记录 移除的记录 窗口内模具 distinct
hi 加入 模具 1,2,2 lo 移除 (时间2<3) {2} 1
hi 加入 模具 3 lo 移除 (时间3<4) {2, 3} 2

答案为 1 2。

代码

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

int main() {
    int n, k, q;
    scanf("%d%d%d", &n, &k, &q);

    vector<int> starts(q);
    for (int i = 0; i < q; i++) scanf("%d", &starts[i]);

    int m;
    scanf("%d", &m);

    vector<int> rtime(m), rmold(m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &rmold[i], &rtime[i]);
    }

    vector<int> idx(m);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b) {
        return rtime[a] < rtime[b];
    });

    vector<int> stime(m), smold(m);
    for (int i = 0; i < m; i++) {
        stime[i] = rtime[idx[i]];
        smold[i] = rmold[idx[i]];
    }

    vector<int> order(q);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return starts[a] < starts[b];
    });

    vector<int> ans(q);
    vector<int> cnt(n + 1, 0);
    int distinct = 0;
    int lo = 0, hi = 0;

    for (int qi : order) {
        int L = starts[qi];
        int R = L + k - 1;

        while (hi < m && stime[hi] <= R) {
            int mold = smold[hi];
            if (cnt[mold] == 0) distinct++;
            cnt[mold]++;
            hi++;
        }

        while (lo < m && stime[lo] < L) {
            int mold = smold[lo];
            cnt[mold]--;
            if (cnt[mold] == 0) distinct--;
            lo++;
        }

        ans[qi] = distinct;
    }

    for (int i = 0; i < q; i++) {
        if (i > 0) putchar(' ');
        printf("%d", ans[i]);
    }
    putchar('\n');
    return 0;
}

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);

        in.nextToken(); int n = (int) in.nval;
        in.nextToken(); int k = (int) in.nval;
        in.nextToken(); int q = (int) in.nval;

        int[] starts = new int[q];
        for (int i = 0; i < q; i++) {
            in.nextToken();
            starts[i] = (int) in.nval;
        }

        in.nextToken();
        int m = (int) in.nval;

        int[] recTime = new int[m];
        int[] recMold = new int[m];
        for (int i = 0; i < m; i++) {
            in.nextToken(); recMold[i] = (int) in.nval;
            in.nextToken(); recTime[i] = (int) in.nval;
        }

        Integer[] ridx = new Integer[m];
        for (int i = 0; i < m; i++) ridx[i] = i;
        Arrays.sort(ridx, (a, b) -> recTime[a] - recTime[b]);

        int[] sortedTime = new int[m];
        int[] sortedMold = new int[m];
        for (int i = 0; i < m; i++) {
            sortedTime[i] = recTime[ridx[i]];
            sortedMold[i] = recMold[ridx[i]];
        }

        Integer[] order = new Integer[q];
        for (int i = 0; i < q; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> starts[a] - starts[b]);

        int[] ans = new int[q];
        int[] cnt = new int[n + 1];
        int distinct = 0;
        int lo = 0, hi = 0;

        for (int idx : order) {
            int L = starts[idx];
            int R = L + k - 1;

            while (hi < m && sortedTime[hi] <= R) {
                int mold = sortedMold[hi];
                if (cnt[mold] == 0) distinct++;
                cnt[mold]++;
                hi++;
            }

            while (lo < m && sortedTime[lo] < L) {
                int mold = sortedMold[lo];
                cnt[mold]--;
                if (cnt[mold] == 0) distinct--;
                lo++;
            }

            ans[idx] = distinct;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            if (i > 0) sb.append(' ');
            sb.append(ans[i]);
        }
        System.out.println(sb);
    }
}

import sys
from collections import defaultdict

def main():
    data = sys.stdin.buffer.read().split()
    pos = 0
    n = int(data[pos]); pos += 1
    k = int(data[pos]); pos += 1
    q = int(data[pos]); pos += 1

    starts = [int(data[pos + i]) for i in range(q)]
    pos += q

    m = int(data[pos]); pos += 1

    rmold = [0] * m
    rtime = [0] * m
    for i in range(m):
        rmold[i] = int(data[pos]); pos += 1
        rtime[i] = int(data[pos]); pos += 1

    idx_sorted = sorted(range(m), key=lambda i: rtime[i])
    stime = [rtime[i] for i in idx_sorted]
    smold = [rmold[i] for i in idx_sorted]

    order = sorted(range(q), key=lambda i: starts[i])

    ans = [0] * q
    cnt = defaultdict(int)
    distinct = 0
    lo = 0
    hi = 0

    for qi in order:
        L = starts[qi]
        R = L + k - 1

        while hi < m and stime[hi] <= R:
            mold = smold[hi]
            if cnt[mold] == 0:
                distinct += 1
            cnt[mold] += 1
            hi += 1

        while lo < m and stime[lo] < L:
            mold = smold[lo]
            cnt[mold] -= 1
            if cnt[mold] == 0:
                del cnt[mold]
                distinct -= 1
            lo += 1

        ans[qi] = distinct

    sys.stdout.write(' '.join(map(str, ans)) + '\n')

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    let ptr = 0;
    const [n, k, q] = lines[ptr++].split(' ').map(Number);
    const starts = lines[ptr++].split(' ').map(Number);
    const m = parseInt(lines[ptr++]);

    const recMold = [];
    const recTime = [];
    for (let i = 0; i < m; i++) {
        const parts = lines[ptr++].split(' ');
        recMold.push(parseInt(parts[0]));
        recTime.push(parseInt(parts[1]));
    }

    const idx = Array.from({length: m}, (_, i) => i);
    idx.sort((a, b) => recTime[a] - recTime[b]);

    const stime = [];
    const smold = [];
    for (let i = 0; i < m; i++) {
        stime.push(recTime[idx[i]]);
        smold.push(recMold[idx[i]]);
    }

    const order = Array.from({length: q}, (_, i) => i);
    order.sort((a, b) => starts[a] - starts[b]);

    const ans = new Array(q);
    const cnt = new Array(n + 1).fill(0);
    let distinct = 0;
    let lo = 0, hi = 0;

    for (const qi of order) {
        const L = starts[qi];
        const R = L + k - 1;

        while (hi < m && stime[hi] <= R) {
            const mold = smold[hi];
            if (cnt[mold] === 0) distinct++;
            cnt[mold]++;
            hi++;
        }

        while (lo < m && stime[lo] < L) {
            const mold = smold[lo];
            cnt[mold]--;
            if (cnt[mold] === 0) distinct--;
            lo++;
        }

        ans[qi] = distinct;
    }

    console.log(ans.join(' '));
});

复杂度分析

  • 时间复杂度：。排序记录和排序查询各需 和 。双指针扫描过程中，lo 和 hi 各自最多移动 次，总共 。
  • 空间复杂度：。存储排序后的记录、查询索引以及计数数组。