代码如下,求大神帮忙给个hack或者看一下哪里错了:
#include <bits/stdc++.h>
using namespace std;
long long n,q,a[200020],x,y,s[200020];
typedef struct b{
long long s,t;
}humor;//s为左界,t为正数位置
vector<humor> hum;
void init(){
for(int i=n,j=n;i>0;i=min(i-1,j)){
if(a[i]>0){
humor h;
h.t=i;
h.s=i;
long long tmp=a[i],p=0;
for(j=i-1;a[j]<=0&&j>0;j--){
tmp+=a[j];
if(tmp<=0&&p==0){
h.s=j+1;
p++;
}
}
if(p==0)h.s=j+1;
hum.push_back(h);
}
}
}//预处理,hum为降序数组,储存左右界
void query(long long x,long long y){
cin>>x>>y;
long long curl,curr;
if(hum.back().t>y){cout<<0<<endl;return;}//特判
else{
int l=0,r=hum.size()-1,mid=(l+r)>>1;
while(l<=r){
mid=(l+r)>>1;
if(hum[mid].t<=y)r=mid-1;
else l=mid+1;
}
curr=mid;
}
if(hum.front().t<x){cout<<0<<endl;return;}//特判
else{
long long l=0,r=hum.size()-1,mid;
while(l<=r){
mid=(l+r)>>1;
if(hum[mid].t>=x)l=mid+1;
else r=mid-1;
}
if(hum[mid].t<x)mid--;
curl=mid;
}
cout<<(s[curr]-s[curl])+(hum[curl].t-max(x,hum[curl].s)+1)<<endl;//前缀和计算
}
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
init();
for(int i=hum.size()-1;i>=0;i--){
s[i]=s[i+1]+hum[i].t-hum[i].s+1;
}//前缀和预处理
for(int i=0;i<q;i++){
query(x,y);
}
return 0;
}