为什么二分的实现方式不同答案不同? 这是wa3的二分:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
long long c[N],need[N],st[N],ed[N],n,m,res,a[N],p[N];
bool check(long long u)
{
    memset(c,0,sizeof c);
    for(int i=1;i<=u;i++) c[st[i]]+=need[i],c[ed[i]+1]-=need[i];
    for(int i=1;i<=n;i++){
        p[i]=p[i-1]+c[i];
        if(p[i]>a[i]) return false;
    }
    return true;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>need[i]>>st[i]>>ed[i];
    if(check(m)) return cout<<0,0;
    long long l=1,r=m;
    while(l<r){
        long long mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<-1<<endl<<l+1;
    return 0;
}

这是ac的:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
long long c[N],need[N],st[N],ed[N],n,m,res,a[N],p[N];
bool check(int u)
{
    memset(c,0,sizeof c);
    for(int i=1;i<=u;i++) c[st[i]]+=need[i],c[ed[i]+1]-=need[i];
    for(int i=1;i<=n;i++){
        p[i]=p[i-1]+c[i];
        if(p[i]>a[i]) return false;
    }
    return true;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>need[i]>>st[i]>>ed[i];
    if(check(m)) return cout<<0,0;
    int l=1,r=m;
    while(l<=r){
        int mid=l+r+1>>1;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    cout<<-1<<endl<<l;
    return 0;
}

还有一个是没过hack的:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
long long c[N],need[N],st[N],ed[N],n,m,res,a[N],p[N];
bool check(int u)
{
    memset(c,0,sizeof c);
    for(int i=1;i<=u;i++) c[st[i]]+=need[i],c[ed[i]+1]-=need[i];
    for(int i=1;i<=n;i++){
        p[i]=p[i-1]+c[i];
        if(p[i]>a[i]) return false;
    }
    return true;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>need[i]>>st[i]>>ed[i];
    if(check(m)) return cout<<0,0;
    int l=1,r=m;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid)) res=mid,l=mid;
        else r=mid-1;
    }
    cout<<-1<<endl<<res+1;
    return 0;
}