题解：P10903 [蓝桥杯 2024 省 C] 商品库存管理
jinhangdong
·
·
题解
前置知识：前缀和、差分
首先我们通过差分得到一个数组 a。
我们发现如果撤销第 i 个操作会让第 x 种商品的库存量为 0 那么只有两种情况：
$2$.所有操作过后第 $x$ 种商品的库存量为 $1$，并且 $x$ 在第 $i$ 个操作区间内。
综上所述撤销第 $i$ 个操作后库存量为 $0$ 的商品的总数为：$\displaystyle\sum_{i=1}^{n}{[a_i=0]} + \displaystyle\sum_{i=l_i}^{r_i}{[a_i=1]}$，这个我们预处理一个前缀和就好了。
最后附上代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,sum,a[300005],s[300005],l[300005],r[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) sum++;//计算所有操作后库存量为0的商品总数
s[i]=s[i-1]+(a[i]==1);// 计算所有操作后库存量为1的前缀和
}
for(int i=1;i<=m;++i) cout<<s[r[i]]-s[l[i]-1]+sum<<endl;//答案是 l[i]~r[i]为1的个数+所有操作后为0的个数
return 0;
}
```