蓝桥杯 商品库存管理

问题描述

在库存管理系统中，跟踪和调节商品库存量是关键任务之一。小蓝经营的仓库中存有多种商品，这些商品根据类别和规格被有序地分类并编号，编号范围从 1 至 n。初始时，每种商品的库存量均为 0。

为了高效地监控和调整库存量，小蓝的管理团队设计了 m 个操作，每个操作涉及到一个特定的商品区间，即一段连续的商品编号范围（例如区间 [L, R]）。执行这些操作时，区间内每种商品的库存量都将增加 1。

然而，在某些情况下，管理团队可能会决定不执行某些操作，使得这些操作涉及的商品区间内的库存量不会发生改变，维持原有的状态。

现在，管理团队需要一个评估机制，来确定如果某个操作未被执行，那么最终会有多少种商品的库存量为 0。对此，请你为管理团队计算出，每个操作未执行时，库存量为 0 的商品的种类数。

输入格式

• 第一行包含两个整数 n 和 m，分别表示商品的种类数和操作的个数。
• 接下来的 m 行，每行包含两个整数 L 和 R，表示一个操作涉及的商品区间。

输出格式

输出格式：
输出共 m 行，每行一个整数，第 i 行的整数表示如果不执行第 i 个操作，则最终库存量为 0 的商品种类数。

样例输入

5 3
1 2
2 4
3 5

样例输出

1
0
1

样例说明

考虑不执行每个操作时，其余操作对商品库存的综合影响：

• 不执行操作 1：剩余的操作是操作 2（影响区间 [2, 4]）和操作 3（影响区间 [3, 5]）。执行这两个操作后，商品库存序列变为 [0, 1, 2, 2, 1]。在这种情况下，只有编号为 1 的商品的库存量为 0。因此，库存量为 0 的商品种类数为 1。
• 不执行操作 2：剩余的操作是操作 1（影响区间 [1, 2]）和操作 3（影响区间 [3, 5]）。执行这两个操作后，商品库存序列变为 [1, 1, 1, 1, 1]。在这种情况下，所有商品的库存量都不为 0，因此，库存量为 0 的商品种类数为 0。
• 不执行操作 3：剩余的操作是操作 1（影响区间 [1, 2]）和操作 2（影响区间 [2, 4]）。执行这两个操作后，商品库存序列变为 [1, 2, 1, 1, 0]。在这种情况下，只有编号为 5 的商品的库存量为 0。因此，库存量为 0 的商品种类数为 1。

评测用例规模与约定

• 对于 20% 的评测用例，1 ≤ n, m ≤ 5 × 10^3，1 ≤ L ≤ R ≤ n
• 对于所有评测用例，1 ≤ n, m ≤ 3 × 10^5，1 ≤ L ≤ R ≤ n

c++代码(差分法)

#include<bits/stdc++.h>
#include<stdio.h>

using namespace std;

int n, m, cont = 0;
vector<int> dir, dp, arr;
vector<vector<int>> ops;

void add(int left, int right) {
    dir[left]++;
    if (right + 1 <= n) dir[right + 1]--;
}

int main() {
    scanf("%d %d", &n, &m);
    dir = vector<int>(n + 1, 0);
    arr = vector<int>(n + 1, 0);
    dp = vector<int>(n + 1, 0);
    ops = vector<vector<int>>(m, vector<int>(2));
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &ops[i][0], &ops[i][1]);
        add(ops[i][0], ops[i][1]);
    }
    for (int i = 1; i <= n; i++) {
        arr[i] = dir[i] + arr[i - 1];
        if (arr[i] == 0) cont++;
        if (arr[i] == 1) dp[i] = dp[i - 1] + 1;
        else dp[i] = dp[i - 1];
    }
    for (int i = 0; i < m; i++) {
        int left = ops[i][0], right = ops[i][1];
        int k = dp[right] - dp[left - 1];
        printf("%d\n", cont + k);
    }
    return 0;
}//by wqs

c++代码(线段树法)

由于数组初始状态数值本来就为0，所以不需要build函数。

#include<bits/stdc++.h>
#include<stdio.h>

using namespace std;

int n, m, a, b, cont = 0;

class tree {
public:
    int val;
    int lazy;
};

vector<tree> trees;
vector<vector<int>> ops;
vector<int> arr, dp;

void passlazy(int p, int l, int r) {
    int mid = (l + r) / 2;
    if (trees[p].lazy > 0) {
        trees[2 * p].lazy += trees[p].lazy;
        trees[2 * p + 1].lazy += trees[p].lazy;
        trees[2 * p].val += (mid - l + 1) * trees[p].lazy;
        trees[2 * p + 1].val += (r - mid) * trees[p].lazy;
        trees[p].lazy = 0;
    }
}

void add(int p, int l, int r, int left, int right) {
    if (l >= left && r <= right) {
        trees[p].val += r - l + 1;
        trees[p].lazy += 1;
        return;
    }
    passlazy(p, l, r);
    int mid = (l + r) / 2;
    if (left <= mid) add(2 * p, l, mid, left, right);
    if (right > mid) add(2 * p + 1, mid + 1, r, left, right);
    trees[p].val = trees[2 * p].val + trees[2 * p + 1].val;
}

int quary(int p, int l, int r, int left, int right) {
    if (l >= left && r <= right) return trees[p].val;
    passlazy(p, l, r);
    int mid = (l + r) / 2, ans = 0;
    if (left <= mid) ans += quary(2 * p, l, mid, left, right);
    if (right > mid) ans += quary(2 * p + 1, mid + 1, r, left, right);
    return ans;
}

int main() {
    scanf("%d %d", &n, &m);
    trees = vector<tree>(4 * n);
    arr = vector<int>(n + 1);
    dp = vector<int>(n + 1, 0);
    ops = vector<vector<int>>(m, vector<int>(2));
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &ops[i][0], &ops[i][1]);
        add(1, 1, n, ops[i][0], ops[i][1]);
    }
    for (int i = 1; i <= n; i++) {
        arr[i] = quary(1, 1, n, i, i);
    }
    for (int i = 1; i <= n; i++) {
        if (arr[i] == 0) cont++;
        if (arr[i] == 1) dp[i] = dp[i - 1] + 1;
        else dp[i] = dp[i - 1];
    }
    for (int i = 0; i < m; i++) {
        int left = ops[i][0], right = ops[i][1];
        int k = dp[right] - dp[left - 1];
        printf("%d\n", k + cont);
    }
}//by wqs

算法解析

得到m次区间加1后的数组

有两种比较好的办法，第一种办法是差分,大致代码如下

void add(int left, int right) {
    dir[left]++;
    if (right + 1 <= n) dir[right + 1]--;
}

for (int i = 0; i < m; i++) {
    scanf("%d %d", &left, &right);
    add(left, right);
}

for (int i = 1; i <= n; i++) {
    arr[i] = dir[i] + arr[i - 1];
}

第二种办法是线段树

由于数组初始状态数值本来就为0，所以不需要build函数。

class tree {
public:
    int val;
    int lazy;
};
vector<tree> trees;

void passlazy(int p, int l, int r) {
    int mid = (l + r) / 2;
    if (trees[p].lazy > 0) {
        trees[2 * p].lazy += trees[p].lazy;
        trees[2 * p + 1].lazy += trees[p].lazy;
        trees[2 * p].val += (mid - l + 1) * trees[p].lazy;
        trees[2 * p + 1].val += (r - mid) * trees[p].lazy;
        trees[p].lazy = 0;
    }
}

void add(int p, int l, int r, int left, int right) {
    if (l >= left && r <= right) {
        trees[p].val += r - l + 1;
        trees[p].lazy += 1;
        return;
    }
    passlazy(p, l, r);
    int mid = (l + r) / 2;
    if (left <= mid) add(2 * p, l, mid, left, right);
    if (right > mid) add(2 * p + 1, mid + 1, r, left, right);
    trees[p].val = trees[2 * p].val + trees[2 * p + 1].val;
}

int quary(int p, int l, int r, int left, int right) {
    if (l >= left && r <= right) return trees[p].val;
    passlazy(p, l, r);
    int mid = (l + r) / 2, ans = 0;
    if (left <= mid) ans += quary(2 * p, l, mid, left, right);
    if (right > mid) ans += quary(2 * p + 1, mid + 1, r, left, right);
    return ans;
}

for (int i = 0; i < m; i++) {
    scanf("%d %d", &left, &right);
    add(1, 1, n, left, right);
}
for (int i = 1; i <= n; i++) {
    arr[i] = quary(1, 1, n, i, i);
}

这两种办法的时间复杂度差不多，编写难度也差不多，只是线段树代码量大。

求出所有加一操作后数值为0的有多少个

if (arr[i] == 0) cont++;

用动态规划求某个区间有多少个1

//dp[i]表示前i个数字1的个数
if (arr[i] == 1) dp[i] = dp[i - 1] + 1;
else dp[i] = dp[i - 1];
//left到right区间1的个数k=dp[right] - dp[left - 1];

直接得出答案

//这样不执行[left, right]的加一操作，会有k + cont个0
//k = dp[right] - dp[left - 1];
//很容易证明，你给[left, right]每个数减一,原来的1会变成0，原来的0已经包含在cont里面,所有我们只关心里面有多少1
for (int i = 0; i < m; i++) {
    int left = ops[i][0], right = ops[i][1];
    int k = dp[right] - dp[left - 1];
    printf("%d\n", k + cont);
}