题解：P10903 [蓝桥杯 2024 省 C] 商品库存管理

· · 题解

题目传送门

思路

设数组 a 为货物数量，不难发现，对于每一次操作，变化的都是连续的一段区间，所以我们可以使用差分来求出最终的 a。

若不执行某次操作，就相当于在最终的 a 的基础上，将下标为 [l[i],r[i]] 的货物数量减 1，所以对于每一次询问，答案即为：

\sum_{i=1}^{n}[a_i=0]+\sum_{j=l_i}^{r_i}[a_i=1]

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,cnt;
int l[300005],r[300005];     //如题
int c[300005],q[300005];     //差分数组与前缀和数组
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>l[i]>>r[i];
        c[l[i]]++;
        c[r[i]+1]--;
    }                        //输入与差分

    for(int i=1;i<=n;i++){
        q[i]=q[i-1]+c[i];
        if(q[i]==0){
            ans++;
        }
    }                        //求最终货物数

    for(int i=1;i<=m;i++){
        cnt=ans;
        for(int t=l[i];t<=r[i];t++){
            if(q[t]==1){
                cnt++;
            }
        }
        cout<<cnt<<endl;
    }                        //求出答案并输出
}

AC记录