问题描述
在库存管理系统中，跟踪和调节商品库存量是关键任务之一。小蓝经营的仓库中存有多种商品，这些商品根据类别和规格被有序地分类并编号，编号范围从 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);
}
