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

cnblogs食用更佳

题目大意

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

解题思路

通过将区间内所有数量增加这句话我们就能很直接的想到差分。

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

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

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

求解公式为：

代码

#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