解题思路:
初始商品库存均为0，执行完全部操作后分为2种情况：
商品库存<=1 //表示被0或1个区间包含
商品库存>1 //表示被1个以上的区间包含
因为每次只能撤回一次操作，等价于求[l,r]<=1的个数，还原差分数组时计算一下区间1的个数的前缀和就解决了
#include<bits/stdc++.h>
using namespace std;
#define pr pair<int,int>
#define fr first
#define sc second
const int N=3*(1e5+5);
int n,m,diff[N],sum[N];
pr op[N];
int main()
{
ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
cin>>n>>m;
for(int i=0;i<m;++i){
int l,r;cin>>l>>r;
++diff[l],--diff[r+1];
op[i]={l,r};
}
for(int i=1;i<=n;++i){
diff[i]+=diff[i-1];
sum[i]=sum[i-1]+(diff[i]<=1);
}
for(int i=0;i<m;++i)cout<<sum[op[i].sc]-sum[op[i].fr-1]<<'\n';
return 0;
}注意事项:
参考代码:
0.0分
3 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
#include <bits/stdc++.h> using namespace std; const int N=3e5+10; pair<int,int>pr[N]; int diff[N],sum[N],ans=0; int main(){ int n,m;cin>>n>>m; for(int i=0;i<m;i++){ int a,b;cin>>a>>b; diff[a]++,diff[b+1]--; pr[i]={a,b}; } for(int i=1;i<=n;i++){ diff[i]+=diff[i-1]; sum[i]+=sum[i-1]+(diff[i]<=1); if(diff[i]==0) ans++;//记录未被操作的商品 } for(int i=0;i<m;i++)cout<<sum[pr[i].second]-sum[pr[i].first-1]+ans<<endl; return 0; }这样就好了