【商品库存管理——差分、前缀和】

题目

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
int l[N], r[N], b[N];
int s1[N], s0[N];
int main()
{int n, m;cin >> n >> m;for(int i = 1; i <= m; i++){cin >> l[i] >> r[i];b[l[i]]++, b[r[i]+1]--;}int a = 0;for(int i = 1; i <= n; i++){a += b[i];s0[i] = s0[i-1] + (a == 0);s1[i] = s1[i-1] + (a == 1);}for(int i = 1; i <= m; i++)cout << (s0[n] - (s0[r[i]] - s0[l[i]-1])) + (s1[r[i]] - s1[l[i]-1]) << '\n';
}