题目大意
给 \(N\) 个时刻：
- 当 \(i\) 为奇数时，\(A_i\) 表示刚刚起床的时刻。
- 当 \(i\) 为偶数时，\(A_i\) 表示开始睡觉的时刻。
有 \(Q\) 次询问，每次求在 \([l,r]\) 区间内睡了多长时间。
分析
首先我们要考虑处理边界情况。
每一次二分查找第一个大于等于 \(l\) 和 \(r\) 的时刻 \(x\) 和 \(y\)。
分别判断 \(x\) 和 \(y\) 是起床还是开始睡觉。
- 如果是起床，则说明上一段时间正在睡觉，就记录贡献。
- 如果是开始睡觉，则说明上一段时间未睡觉，就不用管。
处理完边界条件后就只需要处理中间整段的睡觉时间。
这个用一个前缀和维护即可。
具体细节请看代码。
Code
#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
int n,Q,a[N];
int p[N];
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
p[i]+=p[i-1];//前缀和
if(i%2==1)p[i]+=a[i]-a[i-1];
}
cin>>Q;
while(Q--){
int l,r,ans=0;
cin>>l>>r;
int x=lower_bound(a,a+n,l)-a;//lower_bound查找下一个时刻
int y=lower_bound(a,a+n,r)-a;
if(x%2==1)ans+=a[x]-l;//判断边界贡献
if(y%2==1)ans+=r-a[y-1];
ans+=p[y-1]-p[x];//处理中间部分
cout<<ans<<endl;
}
return 0;
}