题解：商品库存管理

题目描述

在小蓝的仓库中，有 $n$ 种商品，编号从 $1$ 到 $n$。初始时，每种商品的库存量均为 $0$。管理团队设计了 $m$ 个操作，每个操作涉及一段连续的商品编号区间 $[L,R]$，执行该操作会使区间内每种商品的库存量增加 $1$。

现在需要评估，如果某个操作未被执行，则最终会有多少种商品的库存量为 $0$。对于每个操作，计算出如果不执行该操作而执行其他所有操作时，库存量为 $0$ 的商品种类数。

解题思路

核心思想

• 差分数组：通过差分数组快速处理区间更新操作。
• 前缀和统计：利用前缀和统计库存量为 $0$ 和 $1$ 的商品数量。
• 单次查询优化：通过预处理和区间查询，在 $O(1)$ 时间内完成对每个操作的结果计算。

具体步骤

1. 差分数组初始化：

   • 定义一个差分数组 nums，用于记录每个操作对商品库存的影响。
   • 对于每个操作 $[L,R]$，将 nums[L]++ 和 nums[R+1]--，表示区间更新。

2. 还原实际库存量：

   • 使用差分数组还原出每个商品的最终库存量。即通过前缀和计算 numscopy[i] = numscopy[i-1] + nums[i]。

3. 统计前缀信息：

   • 定义两个前缀数组：
     • pre0[i]：表示前 $i$ 个商品中库存量为 $0$ 的商品数量。
     • pre1[i]：表示前 $i$ 个商品中库存量为 $1$ 的商品数量。
   • 在遍历过程中更新这两个前缀数组。

4. 逐一评估每个操作：

   • 如果不执行第 $i$ 个操作，那么区间 $[L_i,R_i]$ 内的商品库存量会减少 $1$。
   • 通过前缀数组快速计算以下两部分：
     • 区间外库存量为 $0$ 的商品数量：pre0[n] - (pre0[R[i]] - pre0[L[i]-1])。
     • 区间内库存量为 $1$ 的商品数量：pre1[R[i]] - pre1[L[i]-1]。
   • 最终结果为这两部分之和。

5. 输出结果：

   • 对于每个操作，输出对应的计算结果。

代码实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static int[] nums;
    static int[] numscopy;
    static int n;
    static int m;

    public static void main(String[] args) throws IOException {
        // 输入商品种类数 n 和操作数 m
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 操作的左右端点数组
        int[] l = new int[m + 5];
        int[] r = new int[m + 5];

        // 差分数组
        nums = new int[n + 5];

        // 处理每个操作
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            l[i] = Integer.parseInt(st.nextToken());
            r[i] = Integer.parseInt(st.nextToken());
            nums[l[i]] += 1;
            nums[r[i] + 1] -= 1;
        }

        // 还原实际库存量
        numscopy = nums.clone();
        int[] pre0 = new int[n + 5]; // 前缀和：库存量为 0 的商品数量
        int[] pre1 = new int[n + 5]; // 前缀和：库存量为 1 的商品数量

        for (int i = 1; i <= n; i++) {
            numscopy[i] += numscopy[i - 1];
            pre0[i] = pre0[i - 1] + (numscopy[i] == 0 ? 1 : 0);
            pre1[i] = pre1[i - 1] + (numscopy[i] == 1 ? 1 : 0);
        }

        // 对每个操作进行评估
        for (int i = 1; i <= m; i++) {
            int res = pre0[n] + (pre1[r[i]] - pre1[l[i] - 1]) - (pre0[r[i]] - pre0[l[i] - 1]);
            out.println(res);
        }

        out.close();
    }
}

示例分析

输入

5 3
1 2
2 4
3 5

输出

1
0
1

分析

1. 不执行操作 $1$：

   • 剩余操作为 $2$ 和 $3$。
   • 商品库存序列为 $[0,1,2,2,1]$。
   • 库存量为 $0$ 的商品种类数为 $1$（编号为 $1$）。

2. 不执行操作 $2$：

   • 剩余操作为 $1$ 和 $3$。
   • 商品库存序列为 $[1,1,1,1,1]$。
   • 库存量为 $0$ 的商品种类数为 $0$。

3. 不执行操作 $3$：

   • 剩余操作为 $1$ 和 $2$。
   • 商品库存序列为 $[1,2,1,1,0]$。
   • 库存量为 $0$ 的商品种类数为 $1$（编号为 $5$）。

时间与空间复杂度

• 时间复杂度：

  • 差分数组更新：$O(m)$。
  • 前缀和计算：$O(n)$。
  • 查询每个操作：$O(m)$。
  • 总时间复杂度：$O(n+m)$。

• 空间复杂度：

  • 差分数组、前缀数组等：$O(n+m)$。

总结

本题通过差分数组和前缀和的巧妙结合，成功将区间更新和查询问题转化为线性复杂度的解决方案。适用于大规模数据场景，能够高效地处理库存管理中的动态变化问题。