自动搬运

查看原文

来自洛谷，原作者为

	jinhangdong 支持互关，有勾就行

搬运于2025-08-24 23:02:22，当前版本为作者最后更新于2024-08-23 16:36:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：前缀和、差分

首先我们通过差分得到一个数组 $a$。

我们发现如果撤销第 $i$ 个操作会让第 $x$ 种商品的库存量为 $0$ 那么只有两种情况：

$1$.所有操作过后第 $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]}$，这个我们预处理一个前缀和就好了。

最后附上代码。

#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;
}