每日一题 7月1日 借教室 二分

题目链接：https://ac.nowcoder.com/acm/problem/16564
题目大意：

思路：线段树的模板题，我们考虑用二分来写。因为是第一个，那么就可以二分了。用差分得到需求。遍历是否满足。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int a[1000005], l[1000005], r[1000005];
LL sum[1000005], s[1000005];
int n, m;
int slove(int x){
    memset(s, 0, sizeof(s));
    for(int i=1; i<=x; i++){
        s[l[i]]+=sum[i]; s[r[i]+1]+=-sum[i];
    }
    for(int i=1; i<=n; i++){
        s[i]+=s[i-1];
        if(s[i]>a[i]){
            return 0;
        }
    }
    return 1;
}

int main(){

    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    for(int i=1; i<=m; i++){
        scanf("%lld%d%d",&sum[i], &l[i], &r[i]);
    }
    int l=1, r=n, k=0;
    while(l<=r){
        int mid=l+r>>1;
        if(!slove(mid)){
            r=mid-1;
            k=mid;
        }
        else{
            l=mid+1;
        }
    }
    if(k){
        printf("-1\n%d\n", k);
    }
    else{
        printf("0\n");
    }

    return 0;
}