AcWing 5994. 商品库存管理(前缀和与差分)
原题链接
中等
思路:统计经过所有操作后商品的数量
不执行某个操作,那最后为0只有两种情况。
1.查询区间内部为1的位置
2.查询区间外为0的位置
那利用前缀和和差分来维护就行了(题目不涉及修改操作)
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 300010;
int n,m;
int l[N],r[N]; //记录每次询问的区间
int s[N],d[N]; //前缀和数组记录每个位置的库存量,差分数组记录变化
int pri[N],pre[N]; //分别记录前n项中0的个数,1的个数
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++){
scanf("%d%d", &l[i], &r[i]);
d[l[i]]++,d[r[i]+1]--;
}
for(int i = 1; i <= n; i++) s[i] = s[i-1]+d[i]; //前缀和计算每个位置的库存量
for(int i = 1; i <= n; i++){
pri[i] = pri[i-1],pre[i] = pre[i-1];
if(s[i] == 0) pri[i]++;
if(s[i] == 1) pre[i]++;
}
for(int i = 1; i <= m; i++)
//查询询问区间内1的个数和区间外0的个数之和,即为答案
printf("%d\n",pri[l[i]-1]+pri[n]-pri[r[i]]+pre[r[i]]-pre[l[i]-1]);
return 0;
}