题解：P10903 [蓝桥杯 2024 省 C] 商品库存管理

题目大意

有一个初始化为 \(0\) 的 长度为 \(n\) 的序列，现有 \(m\) 个操作，每次将区间 \([L, R]\) 中的数量加 \(1\)，求如果不做某个操作将会有多少个数量为 \(0\) 的量。

解题思路

当看见这句话时就想到了差分，这题我们可以使用差分先处理将所有的操作执行后的数组，然后在算出如果减去某个操作的数组是什么样子。

不难想，减去某个操作后数组中 \(0\) 的个数就是区间外本来就是 \(0\) 的量的个数和区间内被变成 \(1\) 的量的个数相加。

这部分代码可以使用前缀和优化。

求解公式为：\(ans_i = \sum_{i = 1} ^ {l_i - 1} {a_i = 0} + \sum_{i = l_i} ^ {r_i} {a_i = 1} + \sum_{i = r_i + 1} ^ {n} {a_i = 0}\)

代码

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

int n, m;
int l[300005], r[300005];
int a[300005], b[300005], c[300005];

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> l[i] >> r[i];
		a[l[i]]++;
		a[r[i] + 1]--;
	}
	
	for (int i = 1; i <= n; i++)
	{
		a[i] += a[i - 1]; // 前缀和
		if (a[i] == 0)
			b[i]++; // 统计为 0
		if (a[i] == 1)
			c[i]++; // 统计为 1
		b[i] += b[i - 1]; // 前缀和
		c[i] += c[i - 1]; // 前缀和
	}
	
	for (int i = 1; i <= m; i++)
	{
		cout << b[l[i] - 1] + b[n] - b[r[i]] + c[r[i]] - c[l[i] - 1] << "\n";
		// 区间外（1~l[i]-1, r[i]+1 ~ n） 为 0 的数 + 区间内为 1 的数。 
	}
	return 0; 
}

// 记录：https://www.luogu.com.cn/record/174366827