P10903（洛谷题面）

题目

题目描述：

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

为了高效地监控和调整库存量，小蓝的管理团队设计了 mm 个操作，每个操作涉及到一个特定的商品区间，即一段连续的商品编号范围（例如区间 [L,R][L, R]）。执行这些操作时，区间内每种商品的库存量都将增加 11。然而，在某些情况下，管理团队可能会决定不执行某些操作，使得这些操作涉及的商品区间内的库存量不会发生改变，维持原有的状态。

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

输入格式：

输入的第一行包含两个整数 nn 和 mm，分别表示商品的种类数和操作的个数。

接下来的 mm 行，每行包含两个整数 LL 和 RR，表示一个操作涉及的商品区间。

输出格式：

输出 mm 行，每行一个整数，第 ii 行的整数表示如果不执行第 ii 个操作，则最终库存量为 00 的商品种类数。

数据范围与说明：

【样例说明】

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

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

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

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

【评测用例规模与约定】

对于 20%20\% 的评测用例，1≤n,m≤5×1031 \le n,m \le 5 \times 10^3，1≤L≤R≤n1\le L \le R \le n。
对于所有评测用例，1≤n,m≤3×1051 \le n,m \le 3 \times 10^5，1≤L≤R≤n1 \le L \le R \le n。

输入输出样例 #1

输入：

1
2
3
4
5 3
1 2
2 4
3 5

输出：

1
2
3
1
0
1

题意

简述：

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

为了高效地监控和调整库存量，小蓝的管理团队设计了 mm 个操作，每个操作涉及到一个特定的商品区间，即一段连续的商品编号范围（例如区间 [L,R][L, R]）。执行这些操作时，区间内每种商品的库存量都将增加 11。然而，在某些情况下，管理团队可能会决定不执行某些操作，使得这些操作涉及的商品区间内的库存量不会发生改变，维持原有的状态。

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

代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int l[300005],r[300005],a[300005],s[300005],sum=0;
int main(){
    int n,m;
    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) sum++;
		s[i]=s[i-1]+(a[i]==1);
	}
    for(int i=1;i<=m;++i) 
        cout<<s[r[i]]-s[l[i]-1]+sum<<endl;
    return 0;
}