求第一个无法满足条件的订单 求最小 可行区开口向右
check中如果mid订单无法满足条件返回true
if(check()) 可行区开口向右 堵住右边 r=mid
循环结束l+1=r r即为所求
r是第一个无法满足条件的订单
l是最后一个满足条件的订单

#include <iostream>
#include <cstring>
#define int long long
const int N=1e6+10;
int n,m,day[N],a[N],b[N],c[N];
int sub[N],sum[N];
using namespace std;
void insert(int c,int l,int r)
{
    sub[l]-=c;
    sub[r+1]+=c;
}
bool check(int mid)
{
    for(int i=1;i<=n;i++)sub[i]=day[i]-day[i-1];
    for(int i=1;i<=mid;i++)insert(a[i],b[i],c[i]);
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+sub[i];
        if(sum[i]<0)return true;
    }
    return false;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&day[i]);
    for(int i=1;i<=m;i++)scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);

    int l=0,r=m+1; //二分枚举订单数量
    while(l+1<r)
    {
        int mid=l+r>>1;
        //求第一个无法满足的订单(求最小的无法满足的订单)check中如果是无法满足的订单则返回false 否则返回true
        if(check(mid))r=mid;  //堵住右边 r=mid
        else l=mid;
    }
    //当l+1=r时退出循环 此时r是第一个无法满足的订单 l是最后一个满足的订单
    if(r==m+1)puts("0");
    else printf("%d\n%lld",-1,r);

    return 0;
}

求最后一个满足条件的订单 求最大 可行区开口向左
check中如果mid订单满足条件返回true
if(check()) 可行区开口向左 堵住左边 l=mid
循环结束l+1=r l即为所求
l是最后一个满足条件的订单
r是第一个不满足条件的订单

#include <iostream>
#include <cstring>
#define int long long
const int N=1e6+10;
int n,m,day[N],a[N],b[N],c[N];
int sub[N],sum[N];
using namespace std;
void insert(int c,int l,int r)
{
    sub[l]-=c;
    sub[r+1]+=c;
}
bool check(int mid)
{
    for(int i=1;i<=n;i++)sub[i]=day[i]-day[i-1];
    for(int i=1;i<=mid;i++)insert(a[i],b[i],c[i]);
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+sub[i];
        if(sum[i]<0)return false;
    }
    return true;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&day[i]);
    for(int i=1;i<=m;i++)scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);

    int l=0,r=m+1; //二分枚举订单数量
    while(l+1<r)
    {
        int mid=l+r>>1;
        //求最后一个满足条件的订单 check中如果满足条件就return ture
        if(check(mid))l=mid;  //堵住左边 l=mid
        else r=mid;
    }
    //当l+1=r时退出循环 此时l是最后一个满足条件的订单 r是第一个不满足条件的订单
    if(l==m)puts("0");
    else printf("%d\n%lld",-1,r);

    return 0;
}